Generation from Noisy Examples
Authors: Ananth Raman
Vinod Raman
Venue: ICML 2025 poster (2025)
Keywords: Learning Theory
Language Generation
Generative Machine Learning
Primary area: theory->learning_theory
TL;DR: We continue to study the learning-theoretic foundations of generation by extending the results from Kleinberg and Mullainathan [2024] and Li et al. [2024] to account for noisy example streams.

Abstract: We continue to study the learning-theoretic foundations of generation by extending the results from Kleinberg and Mullainathan [2024] and Li et al. [2024] to account for noisy example streams. In the noiseless setting of Kleinberg and Mullainathan [2024] and Li et al. [2024], an adversary picks a hypothesis from a binary hypothesis class and provides a generator with a sequence of its positive examples. The goal of the generator is to eventually output new, unseen positive examples. In the noisy setting, an adversary still picks a hypothesis and a sequence of its positive examples. But, before presenting the stream to the generator, the adversary inserts a finite number of negative examples. Unaware of which examples are noisy, the goal of the generator is to still eventually output new, unseen positive examples. In this paper, we provide necessary and sufficient conditions for when a binary hypothesis class can be noisily generatable. We provide such conditions with respect to various constraints on the number of distinct examples that need to be seen before perfect generation of positive examples. Interestingly, for finite and countable classes we show that generatability is largely unaffected by the presence of a finite number of noisy examples.

Generation from Noisy Examples
Ananth Raman Vinod Raman 2
Abstract
in the limit (Gold, 1967), introduced a theoretical model of language generation called "Language Generation the Limit." In this model, there a countable set U of strings and a countable language family C = [ L..... J. where L C U for all i E N. An adversary picks language K E C' and begins to enumerate the strings one by one to the player in rounds t = 1, ..... After observing the string w, in round t E N. the player guesses a string Uh E U in the hope that eú E K {wi..... w, The player has generated from K in the limit, if there exists a finite time step E N such that for all s 2 t, we have that w, K (Wi,.... W The class C is generatable in the limit, if the player can gen- erate from all K E C. Unlike language identification in the limit, Kleinberg & Mullainathan (2024) prove that gener- ation in the limit is possible for every countable language family C.
We continue to study the tcarning-theoretic foun- dations of generation by extending the results from Kleinberg & Mullainathan (2024) and Li et al. (2024) to account for noisy example streams. In the noiseless setting of Kleinberg & Mul- lainathan (2024) and Li et al. (2024), an adversary picks a hypothesis from binary hypothesis class and provides a generator with a sequence of its positive examples. The goal of the generator is to eventually output new, unseen positive examples. In the noisy setting, an adversary still picks a hy- pothesis and sequence of its positive examples. But, before presenting the stream to the generator, the adversary inserts finite number of negative examples. Unaware of which examples are noisy, the goal of the generator is to still eventually out- put new, unseen positive examples. In this paper. we provide necessary and sufficient conditions for when a binary hypothesis class can be noisily gen- eratable. We provide such conditions with respect to various constraints on the number of distinct examples that need to be seen before perfect gen- eration of positive examples. Interestingly, for finite and countable classes we show that gener- atability is largely unaffected by the presence of a finite number of noisy examples.
Kleinberg & Mullainathan (2024)'s positive result has spawned surge of new work, extending the results of Kleinberg & Mullainathan (2024) in various ways (Kalava- sis et al., 2024b; Li et al., 2024; Charikar & Pabbaraju, 2024; Kalavasis et al., 2024a). Of particular interest to us is the work by I.i et al. (2024). They frame the results of Kleinberg & Mullainathan (2024) through dearning-theorett lens by taking the language family C to be a binary hypothesis class H. S {0. 1 defined over some countable instance space X. By doing so, Li et al. (2024) identify stronger notions of generatability, termed "uniform" andd "non-uniform" gen- eratability, and provide characterizations of which classes are uniformly and non-uniformly generatable in terms of new combinatorial dimensions.
1. Introduction
Generation is an important paradigm in machine learning with promising applications to natural language processing (Wolf et al., 2020), computer vision (Khan et al., 2022), and computational chemistry (Vanhaelen et al., 2020). In contrast to its practical applications, a strong theoretical foundation of generation largely missing from literature.
A commonality of Kleinberg Mullainathan (2024) and its follow-up work the assumption that the adversary presents to the player a "noiseless" stream of examples one where every example/string must be contained in the hypothesis/language chosen by the adversary. In practice, such an assumption is unrealistic, as one would still like to generate well even if few examples in the dataset are imperfect. For example, Large Language Models (LLM) are often trained using the potentially hallucinatory outputs of other LLMs (Burns al., 2023; Briesch et al., 2023). More generally, one might want generative model to be robust
Recently, Kleinberg& & Mullainathan (2024), inspired by the seminal work of E Mark Gold on language identification
'Equal contribution BBridgewater-arrtn Raritan Regional High School Universityy of Michigan, Ann Arbor. Correspondence to: Vinod Raman <vkraman& @ umich.edu>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Uniform generatability was also informally considered by Kleinberg & Mullainathan (2024)

---

Generation from Noisy Examples
to data contamination/poisoning attacks (Shang al., 2018; Zhang al., 2023; Jiang al., 2023).
that all countable classes are non-uniformly noise- dependent generatable. Since non-uniform noise- dependent generation implies noisy generation in the limit, this corollary also implies that all countable classes are noisily generatable in the limit. Although not matching, we also provide a necessary condition for non-uniform noise-dependent generation in terms of the Noisy Closure dimension.
Motivated by these concerns, we study generation, in the framework posed by Kleinberg & Mullainathan (2024) and Li et al. (2024), under noisy example streams. In particular, we focus on a simple, but natural noising process: after selecting a positive example stream, the adversary allowed to insert finite number of negative examples in any way it likes, unbeknownst to the player. Such noising process, well as others, have been extensively studied in the context "language identification in the limit" or "inductive inference" (Schäfer, 1985; Fulk & Jain, 1989; Baliga et al., 1992; Jain, 1994; Stephan, 1997; Case et al., 1997; Lange & Grieser, 2002; Mukouchi & Sato, 2003; Tantini et al., 2006). In this paper, we extend this study to generation. To that end, our main contributions are summarized below.
Lemma (Informal). A class H S 10, is non- uniformly noise-dependent generatable only if for ev- ery TI E N, there exists non-decreasing sequence of classes H1 C H2 S _... such that H = U Mi and NC,, (H.)) < oo for all N.
We leave the complete characterization of non-uniform noise-dependent generatability as open question.
(4) We provide two different sufficiency conditions for noisy generatability in the limit. The first shows that (noiseless) non-umin non-uniform generatability is sufficient for noisy generatability in the limit.
(1) We extend the notions of uniform generatability, non- uniform generatability. and generatability in the limit from Kleinberg & Mullainathan (2024) and Li et al. (2024) to account for finite, noisy example streams. We call these new settings "uniform noise-dependent generatability," "non-uniform noise-dependent gener- atability." and "noisy generatability in the limit" re- spectively.
Theorem (Informal). If class S {0, 1) is (noise- less) non-uniformly generatable, then it is noisily gen- eratable in the limit.
Since Li et al. (2024) prove that all countable classes are (noiseless) non-uniform generatable, this result also shows that all countable classes are noisily generatable the limit. In addition, we also give sufficiency condition terms of even stronger notion of noisy generatability called "uniform noise-independent gen- eratability."
(2) We provide a complete characterization of which classes are uniformly noise-dependent generatable in terms of new scale-sensitive dimension call the Noisy Closure dimension.
Theorem (Informal). A class H. S {0, is uni- formly noise-dependent generatable if and only if NC, (H) < oo for every n N, where NC,, (H) is the Noisy Closure dimension of H. at noise-level n.
Theorem (Informal). If there exists a finite sequence of uniformly noise-independent generatable classes H4, He...., H4 such that H = U Hi, then H. is noisily generatable in the limit.
We show that uniform noise-dependent generation is strictly harder than noiseless uniform generation. In fact, we construct a countably infinite class which is trivially uniformly generatable when there is noise, but not uniformly when the adversary is only allowed to perturb a single example. Despite this hardness, we show that all finite classes are still uniformly noise-dependent generatable.
One can think of this latter sufficiency condition as the analog of Theorem 3.10 in Li et al. (2024) which shows that the ability to write class as the finite union of (noiseless) uniformly generatable classes is sufficient for (noiseless) generatability in the limit.
generatable even
While our theorem statements look similar to that of Li et al. (2024), our proof techniques are different due the fact that the Noisy Closure dimension is scale-sensitive. This difference manifests even when characterizing noisy uniform generation. In particular, our uniform generator effectively requires combining different generators for each noise-level whereas the noiseless uniform generator from Li et al. (2024) does not.
(3) We provide a sufficient condition for which classes are non-uniformly noise-dependent generatable.
Lemma (Informal). A class H. S. {0, 13x is non- uniformly noise-dependent generatable if there exists non-decreasing sequence of classes Hi C H2 C ... such that H U H; and (C,(H)) < do for all E N.
1.1. Related Work
Using the result that all finite classes are uniformly nependde generatable, we prove as a corollary
Language Identification in the Limit. In his seminal 1967 paper, E Mark Gold introduced the model of "Language
2

---

Generation from Noisy Examples
Identification in the Limit (Gold, 1967)." " In this model, there is countable set U of strings and countable language family C' = {Li, L..... J. where L; S U for all i E N. An adversary picks language K E C. and begins to enumerate the strings in K one by the one to the player in rounds t == 1,2, .... After observing the string Wi in round t E N, the player guesses an index it. E N with the hope that L. = K. The player has identified K in the limit, if there exists a finite time step t N such that for all 2 t, we have that Li, = K. The class C' is identifiable in the limit, if the player can identify all K E C. Gold showed that while all finite language families are identifiable in the limit, there are simple countable language families which are not. In a follow-up work, Angluin (1979; 1980) provides a precise characterization of language families C' for which language identification in the limit is possible The results by Gold and Angluin emphasized the impossibility of language identification in the limit by ruling out the vast majority of language families. Since Gold's seminal work on language identification in the limit, there has been extensive follow-up work on this model and we refer the reader to the excellent survey by Lange et al. (2008).
hope that vi K (wi....; Wt). The player has generated from K in the limit, if there exists a finite time step E N such that for all 2 t, we have that w. E K') (wi,..., W.). Kleinberg & Mullainathan (2024) prove a strikingly differ- ent result than Gold and Angluin generation in the limit is possible for every countable language family C. This positive result has spurred a number of follow-up works, which we briefly review below.
Kalavasis et al. (2024b) study generation in the stochastic setting, where the positive examples revealed to the gen- erator are sampled i..dd from some unknown distribution. In this model, they study the trade-offs between generating with breadth and generating with consistency and show that in general, achieving both is impossible, resolving an open question posed by Kleinberg & Mullainathan (2024) for a large family of language models. More recently, Charikar & Pabbaraju (2024) and Kalavasis et al. (2024a) further formalize this tension between consistency and breadth by defining various notions of breadth and providing complete characterizations of which language families are generatable in the limit with breadth.
In different direction, and most closely related our work, Li et al. (2024) reinterpret the results of Kleinberg & Mullainathan (2024) through a binary hypothesis class H. S {0, 1}x defined over a countable example space X' By doing so, Li et al. (2024) extend the results of Klein- berg& & Mullainathan (2024) beyond language generation while also formalizing two stronger settings of generation generation. Un- like Kleinberg & Mullainathan (2024) and Kalavasis et al. (2024a) who focus on computable learners and countable language families, Li et al. (2024) place no such restric- tions and provide complete, information-theorer charac- terizations of which hypothesis classes are uniformly and non-uniformly generatable. Li et al. (2024) leave the charac- terization of generatability in the limit as an open question (see Section 4).
Language Identification from Noisy Examples. In addi- tion to the work by Angluin (1979; 1980). different line of follow-up work focused on extending Gold's ss model to account for noisy example streams. There have been several proposed noise models, and we review a few of them here. The most standard noise model for language identification in the limit allows the adversary to first pick an enumera- tion of its chosen language K T. and then insert a fiite number of strings that do not belong to K (Baliga et al., 1992; Fulk& & Jain, 1989; Schäfer, 1985; Case et al., 1997; Stephan, 1997; Lange & Grieser, 2002). We use the term insert to emphasize that every w E K must still be present in the sequence chosen by the adversary. Such noisy streams are often referred to as noisy texts. Jain (1994) go beyond the finite nature of the noise by considering sequences of strings with infinite number of noisy incorrect strings, where the amount of noise is measured using certain density notions. In a different direction, Mukouchi & Sato (2003) and Tantini et al. (2006) model noise at the string-level by defining a distance metric on the space of all strings and allowing the adversaries to insert and delete strings in the original enumeration of K which are at most some distance away from some true string in K.
they term "uniform" and
2. Preliminaries
Let X' denote a countable example space and H S fo, 1 denote a binary hypothesis class. Let X denote the set of all finite subsets of X. Let [N] == {1..... N) and abbreviate finite sequence I1, , Tn as Zim- For any h H. an emumeration of supp(h) is any infinite sequence I1, T2.... such that UleN(Z,)) = shpp(h). In other words, for every x E supp(h), there exists an E N such that v; = x and for every E N, we have that v, E supp(h). For any h E H. a noisy enumeration of supp(h) is any infinite sequence 21, #2, such that for every x E supp(h), there exists an E N such that x; and Ex= 1 (2r & supp(h)) < co. For a finite sequence of examples æ1,-.., xdd and NU {0}. define H(IIain)) == (h E H: (zLa) n ssspp(h)) Z
Language Generation in the Limit. Inspired by large language models and recent interest in generative machine learning, Kleinberg & Mullainathan (2024) study the prob- lem of language generation in the limit. In this problem, the adversary also picks language K E C, and begins to enumerate the strings one by the one to the player in rounds
t= 1,2,... ... However, now, after observing the string w, in round E N. the player guesses string w; E U with the
3

---

Generation from Noisy Examples
d d-... For any class H. define its induced closure operator at noise-level (.HH,n such that
2.1.2. NOISY GENERATION
In the noisy model, we consider the following game, Like before, the adversary picks a hypothesis h H. and se- quence of positive examples 21, 22, E supp(h). But now, the adversary picks noise-level n* E N, and in- serts at most n* negative examples in 21, 22,... to obtain a noisy stream æ1, .2..... The adversary then presents the examples in the noisy stream to generator G one at a time. Without knowledge of the noise-level or the location of the negative examples, the goal of the generator is eventually output new, positive examples ã, E supp(h) (I1,...,,T))
[ (henttnam supp(h), (Fid)u.n := {
if (H n)] 2 1
if [M( m)]
Note that H)),, is exactly the closure operator from Sec- tion 2.1 of Li et al. (2024). We will make the following assumption about hypothesis classes.
Assumption 2.1 (Uniformly Unbounded Support (UUS) (Li et al., 2024)). A hypothesis class H S {0, 13x satis- fies the Uniformly Unbounded Support (UUS) property if supp(h)] = oc for every h E H.
Like the noiseless case, there are several definitions for noisy generatability based on how one quantifies "evvettally."" The most extreme case is what we term "uniform noise- independent generatability."
Remark 2.2. The UUS assumption is mainly needed for bookkeeping purposes to prevent the adversary from ex- hausting all positive examples and thus making the task of generating unseen positive examples impossible. This is consistent with the assumption that each language count- ably infinite in size in the work of Kleinberg & Mullainathan (2024).
Definition 2.4 (Uniform Noise- boiie-Indeeendent Generatabil- ity). Let H C {0, 1} be any hypothesis class satis- rying the UUS property. Then, H is uniformly noise- independent generatable, if there exists a generator g and d' E N, such that for every h E H and any se- quence 21, .2, with E [a & supp(h)) < oo, if there exists t" E N such that K , H = d", then ((IL:)) E supp(h) \ [I,) for all s 2 t
2.1. Generatability
In this paper, we adopt the Bearning-theorees framework for generation introduced by Li et al. (2024). To that end, we define generator as deterministic map from finite sequence of examples to new example.
Here, the generator must perfectly generate after seeing d' E NN examples, where d' can only depend on the class H. itself, and thus is uniform over the noise-level n", the hypothesis h E H. and the stream 31, #2...-.. selected by the adversary. Unsurprisingly, as we show in Section 3.1, uniform noise-independent generatability is impossible even for simple classes with just two hypotheses. In Appendix C, we show this is also the case if we measure sample com- plexity in terms of just the number of distinct positive ex- amples (as opposed to all examples). These results motivate weakening the definition by allowing d' to depend on the leise- We call this setting "Uniform Noise-dependent Generatability."
Definition 2.3 (Generator). A generator is map 9 : x** + X' that takes a finite sequence of examples T2, and outputs new example x.
1.1. NOISELESS GENERATION
In the noiseless setting, an adversary plays a game against generator G. Before the game begins, the adversary picks hypothesis h E 7 and a sequence of examples æ ....... such that {x1, .......> } S supp(h). The adversary reveals the examples as a stream to G one at a time, and the goal of the generator is to eventually output new, unseen positive examples &, E supp(h) \ {x1....,, 21).
Definition 2.5 (Uniform Noise- dependentt Generatability). Let H S {0, 1) be any hypothesis class satisfying the UUS property. Then, H. is uniformly noise- deiieddependentt gen- eratable, if there exists a generator G such that for ev- cry noise-level n² E N, there exists a d* E N, such that for every h E H and any sequence F2,22.... with De 1xx & supp(h)) I n², if there exists t" E N such that (xi,.... zz- } d', then G(T).)) E supp(h) \ (x1,...,.2 J.S for all s 2 t".
Depending on how one quantifies "eventually." one can get various notions of noiseless generatability. For example, if one requires the generator to perfectly generate new unseen examples after observing d E N examples regardless of the hypothesis or stream chosen by the adversary, this is called "uniform generation." " If the number of positive examples required before perfect generation can depend on the hy- pothesis chosen by the adversary, but not the stream, then this is positive examples before perfect generation can depend on both the hypothesis and the stream selected by the adversary, this is called "generation in the limit." We refer the reader to Appendix A for complete definitions and Appendix B for a summary of results.
generation." Finally, if the number of
Uniform noise-dependent generatability does not suffer from the same hardness of uniform noise-independent gen- cratability. In fact, in Section 3.2, we show that all finite classes are uniformly noise-dependent generatable. Nev- ertheless, we can continue weakening the notion of noisy generatability, by allowing d' to also depend on the hypoth-
4

---

Generation from Noisy Examples
esis chosen by the adversary.
eratability.
Definition 2.6 (Non-uniform Noise-dependent Generata- bility). Let H - {o, 11 be any hypothesis class satisfy- ing the UUS property. Then, H is non-uniformly noise- dependent generatable, if there exists generator G, such that for every noise-level n* E N and any h E H. there ex- ists d² E N such that for any sequence 21, 22.... with Di=1 1(2x & supp(h)) I n², if there exists 1* E N such that [æ1..... ] = d", then ((Z1:s) E supp(h) \ {z)....,,,, [. for all 2 t".
Theorem 3.1 (Characterization of Uniform Noise-indepee dent Generatability). Let X be countable and H C {0, 1) satisfy the UUS property. Then, H. is uniformly noise- independent generatable if and only if Nnen supp(h)) oc.
Theorem 3.1 is a hardness result- it shows that even fi- nite classes with just two hypotheses may not be uniformly noise-independent generatable. In fact, one way to interpret Theorem 3.1 is that uniform noise-independent generation is only possible for trivial classes where the generator can perfectly generate without observing any examples from the adversary. Indeed, this is what condition in Theorem 3.1 im- plies, since if this condition is true, the generator can simply compute NAEH supp(h) and always play from this set. In Appendix C, we prove a similar statement even if we only measure the sample complexity in terms of the number of distinct positive examples. Since the sufficiency direction of Theorem 3.1 follows from this observation, we only prove the necessity direction.
The term thon-unifome here is used to refer to the fact that the number of unique examples needed by the generator before perfect generation can depend on the selected h E H. and hence it is "non-uniform" over the hypothesis class, unlike the previous two definitions. Finally, the weakest form of noisy generation allows d to depend on the noise- level, hypothesis, and stream selected by the adversary.
Definition 2.7 (Noisy Generatability in the Limit). Let H S (0. 1)xx be any hypothesis class satisfying the UUS property. Then, H is noisily generatable in the limit, if there exists a generator G, such that for every h E H and any noisy enumeration I1, T2.... of supp(h), there exists e N such that (x1ss) E supp(h)) \ (x1,..., 233 for all 1*.
Proof: (of necessity in Theorem 3.1) Let X' be countable and H. S. 10, satisfy the UUS property. Suppose that supp(h)) =: n < co. We need to show that for every G and sufficiently large d E N, there exists a h E H. and sequence 1 #2... with > 122 & supp(h)) < co, such that for every t E N where [ = d. there exists an 8 2 t such that (frss) & supp(h) \ { (II,..., H.... To that end, fix a generator G and a num- ber d 2 n. Let I1,..., In be the sequence of n exam- ples in NheN supp(h) sorted in their natural order. Pick any sequence of distinct examples In+1, Tnt2........ Id and concatenate them to the end Tim. Let & = G(ria)) and suppose without loss of generality that è $ {zra). Then, by construction, there exists h E H such that å & supp(h). Finally, complete the stream by picking distinct 1 tion, note that Ee 1xx & supp(h)} S d - n < xo. Next, note that t = d is the only time point such that Hai=a]] = d. Finally, note that when s = = d, we have that (z = â & supp(h) \ (=1:.) by definition. If however d < n, then as soon the common intersection Fi.n is enumerated, the generator is forced to produce an output that necessarily lies outside of the support of some hypothesis in H. This completes the proof.
Note that in Definition 2.7, we require the noisy stream picked by the adversary to still contain every example in the support of the selected hypothesis. This is consistent with the model of "noisy texts" from the literature in language identification where one allows the adversary to insert noisy examples in the stream, as opposed to replacing positive examples (Stephan, 1997).
Remark 2.8. The astute reader might notice that there is actually a fifth setting of noisy generatability that we did not cover. In this fifth setting, which we will call "Non-uniform Noise-independent Generatability." the number of positive examples needed before perfect generation can depend on the hypothesis chosen by the adversary, but must still be uniform over the noise-level and the noisy example stream chosen by the adversary. However, as in the case of uni- form coise-independent generatability, non-uniform noise- independent generatability is still too strong as there exists class of just two hypotheses that is not non-uniformly noise- independent generatable. We refer the reader to Appendix D for more details.
S supp(h). First, by construc-
3. Towards Characterizations of Noisy Generation
3.2. Uniform Noise-dependent Generatability
Theorem 3.1 shows that obtaining guarantees that are uni- form over the noise-level is generally hopeless. In this sec- tion, we study the easier setting of uniform deiendee generation, where the number of examples needed for per- fect generation can depend on the noise-level. At a high
3.1. Uniform Noise-independent Generatability
We start by providing a characterization of the strongest form of noisy generation- - uniform indepeedddnndnn gen-
5

---

Generation from Noisy Examples
level, the results in this section extend the techniques from Li et al. (2024) account for noisy example streams. As such, we first define noisy analog of the Closure dimension (see Appendix B for a definition).
eratable, where even simple classes of size two may not be uniformly noise-independent generatable.
Corollary 3.4 (All Finite Classes are Uniformly Noise-de- pendent Generatable). Let X be countable and H S {0, 10. satisfy the UUS property. H. is finite, then H. is uniformly noise-dependent generatable.
Definition 3.2 (n-Noisy Closure dimension). The Noisy Closure dimension of H. at noise-level n E N. denoted NC,(H). is the largest natural number d for which there exist distinct 21,..., Fi E X' such that (#1,....; F-)) H4, + I. and (ai,.... H, < co. If this is true for arbitrarily large d E N, then we say that NC,, (H) = cc. On the other hand, if this is not true for d = 1, we say that (Ht O.
Proof. Let X' be countable and H. S (0, be a finite hypothesis class with q := [7] satisfying the UUS prop- erty. To show that H is uniformly noise desendenn generat- able, it suffices to show that NC.(H) < co for all n E N. For any subset V S H. define (0)v == Onev supp(h) and F = {V C H : [00vl < 20) to be the set of examples common to all hypotheses in V and the sub- sets of H whose intersection of supports has finite car- dinality, respectively. Then, let d == maxver (0)vl be the maximum size of a finite set of examples common to a subset of H. Note that is finite because H is fi- nite. Fix any noise-level n E N and for the sake of con- tradiction, suppose NC,, (H) oo. This means that for every s N. there exists 2 and a sequence of dis- tinct examples .1,...,. De such that (Ii,,.., H.. < co. Pick = ng + d + 1 and consider the stream ,i, such that [x1,-... ",0c,,..,,,,),.,.. _.., < oo for 1 2 8. Recall that H(#1.ri) n) = {h- E H: (,) (supp(h)) 2 t- n.. That is, H(z1;;; n) contains all hypotheses in H that are inconsistent with Z1:t on at most n examples. Since [H((1a;)) I |7| (nq+d+1)- = d+1 distinct examples in 2ia contained in the support of all hypotheses in H(z1.6)). In other words,
Unlike the Closure dimension, the Noisy Closure dimension is scale-sensifive, it is defined with respect every noise- level n E N. Scale-sensitive dimensions are not new to learning theory, but have also been defined and used to characterize other properties of hypothesis classes like PAC and online learnability for regression problems (Rakhlin et al., 2015; Bartlett et al., 1994). Our main theorem in this section uses the Noisy Closure dimension to provide complete characterization of which classes are uniform noise-dependent generatable.
Theorem 3.3 (Characterization of Uniform Noise-depen- dent Generatabilityy. Let X' be countable and H S {0, 1) satisfy the UUS property. Then, H is uniformly noise- dependent generatable if and only if NC, (H) < oo for all N.
Our proof of Theorem 3.3 is constructive. To prove ne- cessity, we consider the case where there exists a n E N such that NC, = xc. Given any generator G and any number of distinct clements d E N, we explicitly pick an E H and a valid noisy stream 21, Z2, such that g makes mistake even after observing d distinct examples. In fact, a simple modification of our proof shows that if NC, (H) = d, then any generator G must observe at least d distinct examples before perfectly generating positive ex- amples when the noise-level is n. To prove sufficiency, we explicitly construct a generator G. which only needs to ob- serve NC,, (7) + distinct examples before being able to perfectly generate when the noise-level is n E N. Crucially, our generator G does not need to know the noise-level picked by the adversary. Together, our necessity and sufficiency directions show that not only does the finiteness of NC,, (H) at every n E N provide a qualitative characterization of uniform noise-dependent generatability, but it also provides a quantitative one- - the "sample complexity" at noise-level E N is ((NC, (H)) - analogous the mistake bound in online learning, which quantifies learnability. We defer the full proof to Appendix E.
q, there are at least t t-ng ng 2
2z)H,, = 100) H()mmm))))) 2 d 1+11 > d. This is a contradiction as d = maxver (0)vl by definition and H)) E F. Thus, NC,, < ng + d + x for all N, completing the proof.
We end this section by establishing that uniform noise- dependent generatability is strictly harder than noiseless uniform generatability. This is similar to online learnabil- ity for classification problems, where typically the noise- free (realizable) and noisy (agnostic) characterizations of learnability are not equivalent for deterministic learning algorithms (Littlestone, 1987; Ben-David et al., 2009).
Lemma 3.5 (Uniform Generatability & Uniform Noise-de- pendent Generatability). Let X be countable. There exists a countable class H. S {0, 1] satisfying the UUS property such that C(H) = 0 but NC, (H) = 00.
Proof. Let P = (P,,P2..... be the set of primes, S, {-q" : n E N}. S = =U,EP S., and X' = P U. Let the support of each hypothesis hn be supp(At,) = Plpjuss and H. := [hp p E PP. Observe that H. satisfies the UUS property and X is countable.
Our characterization of uniform noise-dependent generata- bility in terms of the Noisy Closure dimension allows us to show that all finite classes are uniformly noise- dedeedeeen generatable. This contrasts uniform noise- iiieeenddeeedentt gen-
6

---

Generation from Noisy Examples
We now prove that the Closure dimension (see Appendix B) ((H) 0. Suppose the first element in the sequence is x = -p" for some p E IP and E N. Then ( = } oc. If the first element in the sequence is 21 p E P. then hx = 1-pp n E N } = co. This is because observing any example immediately rules out the one hypothesis that predicts 0 for that example. Note that these are the only two possible cases as it must be the case that T1 E sh) for some h H.
Proof. Since non-uniform noise-dependent generatability implies noisy generatability in the limit, it suffices to show that every countable H. is non-uniformly noise-dependent generatable. Let X' be countable and H S {0.1}* be any countable class satisfying the UUS property. Let h1, h2,...
[f-p" : m E NN]
be some fixed enumeration of H. and define H,, = {/; : S n for all ni E N. Then, observe that Hi C H22 S ... and that H. = U H.s Next, observe that [H, n < oc, which, using Corollary 3.4, implies that NC,, < co. Finally, Lemma 3.6 gives that H is non-uniformly noise- dependent generatable.
Now, we show that NC, (H) = x. Fix some d E N. Con- sider the stream P2. pa of the first d prime numbers. Then, (PI,-- H.1 = |0] = 0, due to the fact that H((p..... Pd; 1) = H and the intersection of the supports of all h E H empty. So, NC, (H) 2 d. Since d E N was picked arbitrarily, this is true for all d E N and therefore, H is not uniformly noise-dependent generatable.
Corollary 3.7 with Lemma 3.5 also establishes that uniform noise-dependent generatability is strictly harder than non- uniform noise-dependent generatability. We now move to our necessity condition for non-uniform noise-dependent generatability.
Lemma 3.5 shows a strong separation between noise-free and uniform noise-dependent generation there a class that is uniformly generatable, but not uniformly noise- dependent generatable even when the adversary is allowed to perturb one example.
Lemma 3.8 (Necessity for Non-uniform Noise-dependent Generatability). Let X' be countable and H S {0. 1)x satisfy the UUS property. If H is non-uniformly noise- dependent generatable, then for every n E NN there exists a non-decreasing sequence of classes H1 E H2 C .... such that H = - H4 and (HH,) < co for all i E.
3.3. Non-uniform Noise-dependent Generatability
Proef. Let X' be countable and H S 10, be any non- uniformly noise-dependent generatable class satisfying the UUS property. Let G be non-uniform noise-dependent generator for H. Fix n E N. For every h E H. let da,n E N be the smallest natural number such that for any sequence Iı, T2,..,... with Exe [z, & supp(h)} S n, if there exists at E N such that [f then ((m)s))
Similar to the characterization of non-uniform generata- bility in the noise-free setting, we can use uniform noise- dependent generatability to provide sufficiency and neces- sary conditions for non-uniform noise-dependent generata- bility.
Lemma 3.6 (Sufficiency for Non-uniform Noise-dependent Generatability). Let X be countable and H. S {0, 1 sat- isfy the UUS property. If there exists a non-decreasing se- quence of classes H2 S. H2 S ... such that H. = U H4 and (H+) so for all i N, then H is non-uniformly noise deieeddeeennent generatable.
dh,n- supp(h) \ {a1,..., ".. for all t. Let H. (h E H du, S ii] for all E N. Note that =
H = USEN Hi because da,n < o for all h E H. More- over, we have that Hi S H4t1 for all i E N. Finally, for every i E N, observe that 9 is a uniform generator for H. at noise-level n E N, implying that (H,,) < i < cc.
To prove Lemma 3.6, we construct a non-uniform noise- dependent generator G, which at each round N, com- putes an index i, E N based on the number of distinct examples seen in the stream so far. G then computes the noisy closure of H., at Level-Level i, and then plays from this set. We defer details to Appendix F.
Note the sufficiency and necessary conditions in Lemmas 3.6 and 3.8 respectively are not matching. Indeed, the con- dition in Lemma 3.6 stronger than that in Lemma 3.8. We leave as an open question a complete characterization of non-uniform noise-dependent generatability.
As a corollary of Lemma 3.6 and Corollary 3.4, we can show that all countable classes are non-uniformly noise- dependent generatable, and hence noisily generatable in the limit. In some sense, this result shows that amongst countable classes, noisy generation comes for free!
3.4. Noisy Generatability in the Limit
Corollary 3.7 showed that all countable classes are noisily generatable in the limit. Here, we provide alternate suffi- ciency conditions for noisy generatability in the limit. Our first result shows that (noiseless) non-uniform generatability is sufficient for noisy generatability in the limit. Since all countable classes are (noiseless) non-uniform generatable (Li et al., 2024), this result also shows that all countable classes are noisily generatable in the limit.
Corollary 3.7 (All Countable Classes are Noisily Non-uni- formly Generatable). Let X be countable and H C {0, 1 satisfy the UUS property. If is countable, then H is non- uniformly noise- desendent generatable, and therefore also noisily generatable in the limit.
7

---

Generation from Noisy Examples
Algorithm 1 Generator G
Suppose that & outputs 25 for some E [ra]. If j < Ta then it must be the case that Line 7 fired and so by con- struction 2j E supp(h") \ (II) Thus, suppose Ta then it must be the case that ( 2,, 1 (01,..., Fr....,,r.--, -r.-.... 1) Accordingly, we have that (dr,....,22. 2f...., 24 = fz1....,, ......,,, which means that #,, E supp(h") (Er,,.................... ,.. ,,...,,, -,,,,,111 and therefore 22, supp(h") \ (.1,,..,, T.). Thus, in ei- ther case, 9 perfectly generates on round 8. Since s* is arbitrary, our proof is complete.
Input: Hypothesis class H. and non-uniform generator Q for t = 2,..... do
Adversary reveals example 22
that j = r, If
Let de = {z1,... (21,..., J and r. S t be the largest time point such that ... x = 2
Initialize of = (()re)
for
i = 1, r do
if a $ (.i,.... It then
g outputs 2 and moves to next round.
else
Update 244 Q( T4 2
In similar spirit to Theorem 3.10 from Li et al. (2024), we provide another sufficiency condition for noisy generata- bility in the limit in terms of uniform noise-independent generatability.
end if end for g outputs 2/ and moves to next round. end for
Theorem 3.10. Let X be countable and H S {0,1]x sat- isfy the UUS property. there exists a finite sequence of uni formly noise- noise-independent generatable classes HH....., He such that H = U Hi, then H. is noisily generatable in the limit.
Theorem 3.9 (Non-uniform Generatability
Noisy Generatability in the Limit). Let X be countable and H. S (0.1)* be any class satisfying the UUS property. If H is (noiseless) non-uniformly generatable, then H is noisily generatable in the limit.
The proof of Theorem 3.10 is similar to the proof Theorem 3.10 from Li et al. (2024) and so we defer it to Appendix G.
Proof. Let X' be countable and H C (0, 1) be any class satisfying the UUS property. Consider the generator G, which uses a non-uniform generator Q as in Algorithm 1.
4. Discussion and Open Questions
In this paper, introduced several notions of noisy gener- atability and made progress towards characterizing which classes are noisily generatable. We highlight some impor- tant directions of future work.
We will show that 9 noisily generates from H. in the limit.
Let h² E H and T2,... be the chosen hypothesis and noisy enumeration of supp(h") picked by the adversary, respectively. Let dgth+ E IN be the number of noiseless distinct examples that Q needs for h" to perfectly generate from supp(h"). Let 1* E N be such that for all / 2 1", we have that 2, supp(h"). Such a t" must exist because there are at most a finite number of noisy examples in the stream. Also, because Z1, Z2.... is noisy enumeration, at some point 8* E N. rs- 2 L' and | - 2 dg(h*). ). Fix some s 2 s*, We will prove that 9 generates perfectly on round s. First, we claim that for all E [r,], we have that if E supp(h*) \ {or,..... ........;f..:
Characterizations of Non-uniform Noise-dependent Gen- eratability and Noisy Generatability in the Limit. An im- portant direction of future work is provide a complete and concise characterization of which classes non- -nifuolfrrmly noise-dependent generatable and noisily generatable in the limit. Note that Li et al. (2024) also pose the complete char- acterization of (noiseless) generatability in the limit as an open question, but do provide a complete characterization of (noiseless) non- non-uniform generatability. We conjecture that the correct characterization of non-uniform nepeennt generatability will need to go beyond sufficiency and necessity conditions in Section 3.3.
, Our proof will be by induction. For the base case, consider i 1. We need to show that of E supp(h() (ur,...., However, this just follows from the fact that ef = Q(Ir.:)), [Irr,,..., I.DI 2 do(h"), and f2r.....,,,I S supp(h*). Next, for the induc- tion step, suppose that for all i S m, we have that 2f supp(ht)) \ (ar....., Lo. 24............. ..,....... ......,f.1 1. Then, by def- inition, we have that 1 = Q(Er........ Fz, 29, The proof of the claim is complete after noting that (Ir.,..., Io, HIr.....,, Lz, 24 H 2 dh()..
Noisy Generatability in the Limit via Membership Or- acles. In addition to showing that all countable classes are generatable in the limit, Kleinberg & Mullainathan (2024) provide a computable algorithm for doing so when given access
membership oracle. membership ora- cle, On H. x X + {0, 1}. takes as input hypothesis h E H and an example E X' and outputs 1 (h(r) = 1}. Although we show that all countable classes are also nois- ily generatable in the limit, the focus of this paper was commation-thhorette in nature. This motivates our next open question. Given access to membership oracle, does
S supp(h*) and
Now we will complete the overall proof by showing that the output of g on round lies in supp(h*) (#1...,,
8

---

Generation from Noisy Examples
there exists a computable algorithm that can noisily generate in the limit from any countable class?
Charikar, M. and Pabbaraju, C. Exploring facets of language generation in the limit. arXiv preprint arXiv:2411.15300 2024.
1,
Acknowledgements
Fulk, M. and Jain, S. Learning in the presence of inaccurate information. 1989.
The authors thank anonymous reviewer gxU2 for catching a bug in Theorem 3.1 and providing a fix. VR acknowl- edges support from the NSF Graduate Research Fellowship Program (GRFP).
Gold, E. M. Language identification in the limit. Informa- tion and control, 10(5):447-474) 1967.
Jain, S. Program synthesis in the presence of infinite number of inaccuracies. In International Workshop Analogical and Inductive Inference, pp. 333-348. Springer, 1994.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Jiang, S., Kadhe, S. R., Zhou, Y., Cai, I.., and Bara- caldo, N. Forcing generative models to degenerate ones: The power of data poisoning attacks. arXiv preprint arXiv:2312.04748, 2023.
References
Kalavasis, A., Mehrotra, A., and Velegkas, G. Characteriza- tions of language generation with breadth. arXiv preprint 2r12i:2242..1 18530, 2024a.
Angluin, D. Finding patterns common to set of strings. In Proceedings of the eleventh annual ACM Symposium Theory of Computing, pp. 130-141, 1979.
Kalavasis, A., Mehrotra, A., and Velegkas, G. On the limits of language generation: Trade-offs between hallucination and mode collapse. arXiv preprint arXiv:2411 2tfi:22411.9900 1.09642, 2024b.
Angluin, D. Inductive inference of formal languages from positive data. Information and control, 45(2):117-135, 1980.
Khan, S., Naseer, M., Hayat, M., Zamir, W., Khan, S., and Shah, M. Transformers in vision: A survey. ACM computing surveys (CSUR), 54(10s): 2022.
Baliga, G., Jain, S., and Sharma, A. Learning from multiple sources of inaccurate data. In Analogical and Induc- tive Inference: International Workshop All '92 Dagstuhl Castle, Germany, October 5-9, 1992 Proceedings 3. pp. 108- 128. Springer, 1992.
Kleinberg, J. and Mullainathan, S. Language generation in the limit. arXiv preprint urXiv:2404.06757,000 2024.
Bartlett, P. L., Long, P. M., and Williamson, R. C. Fat- shattering and the learnability of real-valued functions. In Proceedings of the seventh annual conference on Com- putational learning theory, pp. 299-310, 1994.
Lange, S. and Grieser, G. On the power of incremental learning. Theoretical Computer Science, 288(2):277-3077, 2002.
Lange, S., Zeugmann, T., and Zilles, S. Learning indexed families of recursive languages from positive data: survey. Theoretical Computer Science, 397(1-3):19-- 232, 2008
Ben-David, S., Pál, D., and Shalev-Shware S. Agnostic online learning. In COLT, volume 3, pp. 1, 2009.
Briesch, M., Sobania, D., and Rothlauf, F. Large lan- guage models suffer from their own output: An anal- ysis of the self-consuming training loop. arXiv preprint arXiv:2311.1682 2023.
Li, J., Raman, V., and Tewari, A. Generation through the lens of learning theory. arXiv preprint arX1v:2410.13714, 2024.
Burns, C., Izmailov, P., Kirchner, J. H., Baker, B., Gao, L.., Aschenbrenner, L., Chen, Y., Ecoffet. A., Jogickar, M., Leike, J., et al. Weak-to-strong generalization: Eliciting strong capabilities with weak supervision. arXiv preprint /2.0099, 2023.
Littlestone, N. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285-318, 1987.
Mukouchi, Y. and Sato, M. Refutable language learning with neighbor system. Theoretical computer science, 298(1):89-110, 2003.
Case, J., Jain, S., and Sharma, A. Synthesizing noise- tolerant language learners. In Algorithuiic Learning The- ory: 8th International Workshop, ALT'97 Sendai, Japan, October 6-8, 1997 Proceedings 8, pp. 228-243. Springer, 1997.
Rakhlin, A., Sridharan, K., and Tewari, A. Sequential com- plexities and uniform martingale laws of large numbers. Probability theory and related fields, 161:111-11 2015.

---

Generation from Noisy Examples
Schäfer, G. Some results in the theory of effective program synthesis: Learning by defective information. In Inf. Spring School on Mathematical Methods of Specification and Synthesis of Software Systems, pp. 219-225. Springer, 1985.
Shang, M., Fu, Z., Peng, N., Feng, Y., Zhao, D., and Yan, R. Learning to converse with noisy data: Generation with calibration. In IJCAI, volume 7, 2018.
Stephan, Noisy inference and oracles. Theoretical Com- puler Science, 185(1):129-157, 1997.
Tantini, F., de La Higuera, C., and Janodet, J.-C. Iden- tification in the limit of systematic-noisy languages. In Grammatical Inference: Algorithmss and Applica- tions: 8th International Colloquium, ICGI 2006, Tokyo, Japan, September 20-22, 2006. Proceedings 8, pp. 19-31. Springer, 2006.
Vanhaelen, Q.. Lin, Y.-C., and Zhavoronkov, A. The ad- vent of generative chemistry. ACS Medicinal Chemistry Letters, 1188):496--1000 2020.
Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, Rault, T., Louf, R., Funtowicz, M., et al. Transformers: State-of-the-ar natural language processing. In Proceedings of the 2020 conference pirical methods in natural language processing; system demonstrations, pp. 38-45. 2020.
Zhang, S., Qian, Z., Huang. K., Zhang, R., Xiao, J., He, Y., and Lu, C. Robust generative adversarial network. Machine Learning, 133(1)15135-5161, 2023.
10

---

Generation from Noisy Examples
A. Definitions of Noiseless Generation
Definition A.1 (Uniform Generatability (Li et al., 2024)). Let H S {0, 1I be any hypothesis class satisfying the UUS property. Then, H. is uniformly generatable, if there exists generator 9 and d' E N, such that for every E H. and any sequence Ti, .2.... with {r1, (2,....... S supp(h), if there exists t* E N such that (. } d", then (21:s) supp(h) \ ..21.....22.. ).)) for all 2 t*
Definition A.2 (Non-uniform Generatability (Li et al., 2024)). Let H S 10, be any hypothesis class satisfying the UUS property. Then, H. is non non-unifommee uniformly generatable if there exists a generator G such that for every h E H. there exists a d' E N such that for any sequence 21,"2 22........ with (I1, x2,...) S supp(h), if there exists 1" E N such that [( Tzz H = d',
then (( E supp(h) \ (zI,..., x,} } for all s 2 t*
Definition A.3 (Generatability in the Limit (Li et al., 2024)), Let H. S {0, 1)xt be any hypothesis class satisfying the UUS property. Then, H is generatable in the limit if there exists a generator 9 such that for every h E H. and any enumeration supp(h), there exists a 1 N such that (I))s) supp(h) \ (.1,,...;3.)) for all 2 L*.
T2,.... of
B. Summary of Results for Noiseless Generation
In the noiseless setting, Kleinberg& & Mullainathan (2024) initiated the study of generation in the limit by showing that all countable classes are generatable in the limit and that all finite classes are uniformly generatable. Following this result, Li et al. (2024) provided a complete characterization of uniform generation in terms of a new combinatorial parameter termed the Closure dimension.
Definition B.1 (Closure dimension (Li et al., 2024)). The Closure dimension of H. denoted C(H), is the largest natural number d E N for which there exists distinct 21...., It E X such that (Z1,..., ..)) H.)H. H.O * 1 and [ai,..., xt)nool < co. If this is true for arbitrarily large d E N, then we say that C(H) co. On the other hand, if this is not true for d = 1, we say that C(H) = 0.
In particular, a class is uniformly generatable if and only its its Closure dimension is finite. Theorem B.2 (Theorem 3.3. in Li et al. (2024)). A class H. S {0, 1)x is uniformly generatable if and only if C(H) < oc.
In addition, Li et al. (2024) defined an intermediate setting termed non-uniform generatability, and provided a complete characterization of which classes are non-uniformly generatable.
Theorem B.3 (Theorem 3.5 in Li et al. (2024)). A class H (0, is non-uniformly generatable if and only if there exists non-decreasing sequence of classes Hi C H2 C ... such that H = U H. and C(H.) < 3o for every E N.
As a corollary, Li et al. (2024) establish that all countable classes are actually non-uniformly generatable. Charikar & Pabbaraju (2024) also established this result independently. With regards to generatability in the limit, Kleinberg & Mullainathan (2024) prove that all countable classes are generatable in the limit. Li et al. (2024) provide an alternate sufficiency condition in terms of the Closure dimension.
Theorem B.4 (Theorem 3.10 in Li al. (2024)). A class H. S {0, 13* is generatable in the limit if there exists a finite sequence of classes Hi, H2,.. H. such that H U Hi and C(H,,) do for all i [n].
In this paper, we provide analogous results for noisy generation in terms of a different combinatorial parameter termed the Noisy Closure dimension.
C. An Alternate Version of Uniform Noise-independent Generatability
In this section, we consider an alternate (weaker) version of uniform indieeinddeendent generatability by measuring the sample complexity only in terms of the valid positive examples observed.
Definition C.1 (Alternate Uniform Noise Indee-nndeenn Generatability). Let H S 1)x be any hypothesis class satisfying the UUS property. Then, H is uniformly noise- iniee-indeenndet generatable, if there exists generator G and d' E N, such that for every h E 7l and any sequence Z1, .2... with Ee Hxx & supp(h)} < co, if there exists t* E N such that [xI,,..,, Ze- O supp(h)] = d², then ((T E supp(h) \ {x), (x),..., }.} for all 8 2 L*
Note that the only difference between Definition C.I and D.1 is how d' is measured. In Definition C.I, dd captures only the number of distinct positive examples the stream, while d' in Definition D.I measures the total number of distinct examples

---

Generation from Noisy Examples
in the stream. We start off by proving a simple necessity condition for our alternate notion of uniform noise-independent generatability.
Lemma C.2 (Necessary condition for Altemnte Uniform doise-independent Generatabilityy. Let X be countable and H S {0, 13x satisfy the UUS property. If there exists a subclass F S H and hypothesis I E F such that INEE supp(h)] < oo
and NhEAr(r) supp(h) = -0, then H is not uniformly noise-independent generatable according to Desinition C.I.
Like Theorem 3.1, Lemma C.2 is a hardness result- it shows that finite classes with just two hypotheses may not be uniformly deieeiindeeendent generatable even when the sample complexity is measured in terms of positive example.
Proof. (of Lemma C.2) Let X be countable and H. - {0, 11xh satisfy the UUS property. Let F S H. be any subset of H. such that Nhe shpp(h) < and for which there exists an f E F such that (Neern supp(h) = co. We need to show that H. is not uniformly noise coiss-independent generatable. We will show that F is not uniformly noise- boise-independent generatable which will imply that H is not uniformly indeeeindeeendent generatable. To that end, we need to show that for every 9 and any d E N. there exists a E F and a sequence I1, 22,,.. with Σ>= [x & supp(h)} < oc, such that for every E N where [æ1,... ... n supp(h)) = d, there exists an s 2 such that (x11=)) & supp(h) fæ1...., .. To that end, fix generator G and number d N. Let 21.-.... Fd be sequence of d unique examples in NNEF(()) supp(h). Let 21, 21,-..., Pd be any d unique examples in supp(/) \. NNEZ supp(h) and consider the sequence of 2d unique examples obtained by concatenating 21, .1...... 2d to the end of Ti...., Fd. Denote this new sequence by 21:2d. Let q = IAner supp(h)) sunp(h)) and let vi.... U9 be its elements sorted in its natural order. Concatenate u1.-... Uy to the end of 21:24 and denote this new sequence of unique examples 21:2d+g- Observe that for every h F, we have that suup((h) n (x1,...x24+qh H 2 d. Let u24+; = ( (2d+g) ) and suppose without loss of generality that E2d+g $ be a be hypothesis such that @2d+q & supp(h"). Such a hypothesis must exist because 22d+q & (e1...,,T2244) and Nhe supp(h) S (xi,..., F2d+g77 ). Let F2d- #2d+g+2, be any completion of the stream such that (12d+a+)) supp(h") and {228-g-1)
}
Let h E F
100 S
) = 0.
We are now ready to complete the proof. Let ht* and xı, T2.... be the hypothesis and sequence chosen above. Then, by definition, observe that Ex [z,, & supp(h"))
EirT" 1(x, & supp(h")} S d < co. Moreover, we also know that supp(h") n {xi....,, F2d+g]l 2 d and the first 2d examples are distinct, implying that there exists exactly one time point 1 < 2d + q such that supp(tt") n (xi,....2a 222+731 = d. Finally, noting that 2d + 2 L and that (Z x2d+g) & supp(h") (oop(h"")(=,........ .2.h....,,,.... completes the proof that F is not uniformly noise- poise-independent generatable since G and d were chosen arbitrarily.
Finally, Theorem C.3 provides a full characterization of uniform noise-independent generatability (Definition D.I in terms of the noisy closure dimension.
Theorem C.3 (Characterizationn of Uniform Noise ioise-independent Generatability). Let X be countable and H S {0, 1}* satisfy the UUS property. Then, H is uniformly noise-independder generatable if and only if sup, (NCnNN nn) < cc.
As the proof follows similar techniques as those in the main text, we only provide the proof sketch here.
Proof. (sketch of Theorem C.3) For the necessity direction, suppose that sup,, (NC,,, - n) = co. Then for ev- ery d E N. we can find a at 2 d and sequence 2I,..., such that [ z1)H, < co. Hence, by padding T4 with any remaining elements in (f1),.,,,)),,,r-- we can force the Generator to make a mistake while ensuring that the hypothesis chosen is consistent with at least d examples in the stream. For the sufficiency direc- tion, if sup,, (NC, (H) - n) < oo, then there exists a E N such that for every 2 d and distinct Ii,,.., Lt, we have that either (#1. (.., H.dd = I or (.
oc. Thus, the algorithm which for t 2 d plays from D2)H,, \ {31,...,22) ] if D.),,,-)) 1 is guaranteed to succeed.
D. The Hardness of Non-uniform Noise-independent Generatability
As alluded to in Remark 2.8 there is a fifth setting of noisy generation, which we did not define in the main text. In this setting, the "sample complexity" of the generator can be non non- mon-uniform over the class H. but must still be uniform over the novse-level and stream picked by the adversary. We define this formally below.
12

---

Generation from Noisy Examples
Definition D.1 (Non-uniform Noise-inde Generatability). Let H C {0, 11 UUS property. Then, H is non-uniforaly noise-independent generatable, if there exists generator such that for every h E H. there exists d' E IN such that for any sequence T2,,,,,... with
L be any hypothesis class satisfying the
11 1a & supp(h)} < co,
if there exists 1* IN such that (xi, (x1,..,, Te- supp(h)] d", then (z E supp(h) \ (fi,..,;aa) for all t*.
Unfortunately, non-uniform indeeeedddnn generatability is still a restrictive property as not all finite classes are non-uniformly noise-independent generatable. This in contrast to uniform noise-dependent generatability as shown by Corollary 3.4.
Lemma D.2 (Not All Finite Classes are Non-uniformly Noise inddeeeedeeendent Generatable). Let X be countable. There exists a finite class H S (0, 13 which satisfies the UUS property that not non-uniformly noise-independent generatable.
Proof. Let X = N and consider the class 7/ = {he, ho) such that (x() = f is even) and ho(z) = 1 x is odd). We will show that H is not non-uniformly noise-independet generatable. We need to show that for every generator G. there exists hypothesis h such that for every E there exists a sequence 21, .2,... with
Σ 1f $ supp(h)) < co,
so that for every t e N such that (1)p....., = d. there exists a 2 t where (x11:)) & supp(h) \ Mri....,,, x To that end, fix generator G. Let numbers in S is finite (2) the number of odd numbers in S is finite and (3) there are infinite number of both even and odd numbers in S. Cases (1) and (2) are symmetric. So, without loss of generality, it suffices only to consider Cases (1) and (3),
NeN There are three cases to consider: (1) the number of even
Starting with Case (1), let E N be the smallest time point such that for all t 2 p. we have that G(1..... f) is odd. We will pick hg to use for the lower bound. Fix some d E N. Consider the sequence 21, Z2,... such that i for all i S max (p, 2d} and x; = 2i for all > max 2d}. Note that
Σ af & supp(h.)) S max(p: 2d} < 20.
2
Suppose 2d < p. Then, observe that only on time point t = 2d do we have that [æ1...., 2.. n supp(he)) = d. However, by definition, on time point 8 = p 2 2d = f, we have that g (x11...., Ix) is odd and therefore not in supp(he). Suppose that 2d 2 p. Then, like before, only on time point = 2d do we have that [x n supp(he)) = However, by definition, also on time point s 2d 2 p. we have that ( 2x) ) is odd and therefore not in supp(h.). Since N arbitrary, this true for all d N. completing the proof for Case (1). As mentioned before, the proof for Case (2) follows by symmetry.
We now consider Case (3). For this case, we will pick he for the lower bound. Fix some d E N. Let 2 2d be the smallest time point after and including time point 2d such that (1,,2,... is odd. Such p e N must exist since S contains an infinite number of odd numbers. Now, consider the sequence 3T, Ø2, such that 2; = i for i S and x; = 2 for all i > p. Note that
Σ I far & supp(h.))
P s 2/2 < xc. 2
Observe that only at time point t 2d do we have that [2],.... Fy Ssupp(ha)) = d. However, by definition, also on time point s = 2 2d = t, we have that G( xp) is odd and therefore does not lie in supp(he).. Since E N is arbitrary, this is true for all d E N, completing the proof for Case (3) and the overall proof.
13

---

Generation from Noisy Examples
E. Proof of Theorem 3.3
Proof. (of necessity in Theorem 3.3) Let X' be countable and H C {0, 1j satisfy the UUS property. Suppose there exists a E N such that NC, = oo. We need to show that this means that H. is not uniformly noise-dependent generatable. In particular, we need show that for every generator G. there exists a noise level n* E N such that for every d e I,, there exists hypothesis h E H and sequence 21, 12,22,.... with Σi= 1f supp(h)} I n², so that for every E N with (zi,..., 2 = d, there exists 2 I where (1r:s)) & supp(h) \ (21,..., x..). To that end, let G be any generator and consider the noise level n² = n so that NCx- (H) = oc. Fix any d E N. We will now pick such a hypothesis h" e H and a valid stream F1, 22,22,....
Since NC (H) = oc, we know there exists a d 2 d and a sequence of distinct examples æi,..... Lat such that (F1,...,, ..d (124)Ro Hn, # i and (a11..., FT. Ta, < oc. Let q = (xi,...; Fat "aaii,.....,........ H., \ (x1,..., , } and 21, ................................ By be the elements of (31....,,E'" H, \ Ta. sorted in their natural order. Let a 1.d"++9 denote the sequence obtained by concatenating 21,...,,2 2g to the end of z1, Edr. Let 22-+9 ((x1:d++g) and suppose without loss of generality that +g Let h' E H(Iraas n²) be any hypothesis such that ha-+q & supp(h"). ). Such hypothesis must exist because &. +q $ (=1....; Id +g]
+g $
and (#1,..., Fa ) C (x1,...,,&ee + Finally, let +4++ Ld +q+2:... be any completion of the stream such that (Id Joc E supp(h") and (au-+o+))E J n {xe] 14" =0
We now complete the proof. Let h* and x1, 22.... be the hypothesis and stream chosen above. First, observe that
d'
1 (as & supp(h*)) = Σ 1zz & supp(h")) sn' 1=1
Second, there exists only one E N, namely i = d, such that stream are distinct by construction. However, observe that by construction, time point s = d" + g 2 d, we have that (Z) x.)) = +g
= d, as the first d' + 1 > d examples of the
t & supp(h") \ (=I,..., 3 by choice of h², Since G and d E N were picked arbitrarily, this is true
for all G and d E N, which completes the proof.
Proof. (of sufficiency in Theorem 3.3) The key intuition is that the generator, without knowing the adversary's 's noise level, continually computes the largest noise level for which it has observed enough unique examples to generate perfectly, Eventually, its calculated noise level will surpass and thus account for the adversary's 's noise level, ensuring that the generator is perfect from then on.
Let X' be countable and H S {0. 13.* satisfy the UUS property. We need to show that if NC, (H) < oo for all n E N, then H uniformly noise-dependent generatable. For sequence æ , ........ let de := (xi,...... ... examples amongst the first t examples. Consider the following generator G. At time t E N, G computes ne := max (n e \ 22, ................................ .t)-
denote the number of distinct
[t] (H)) < 4.) U {0). If n, 0, 9 plays any x E X. Otherwise, it plays from (x Ft) We now show that G is a uniform deieedde generator. To that end, let n E .N be the noise level chosen by the adversary. We claim that G can perfectly generate after observing max max(NC, (NC,. (HL + 1,, distinct examples. To see why, let h E H. be any hypothesis, and Z1, ...... be any stream such that Σ 1 [x & supp(h)} S n*t Without loss of generality, suppose there exists 1* E N such that di- = max (NC,, (H) + 1, Observe that t" 2 n² Fix any 2 t*. By definition of ne, it must be the case that n, 2 n². Thus, h E H(=1..... Tg, m2,) and Ft......4,)H., Moreover, because d, NC., (H), again by definition, it must be the case that K Iss H.,,
S &supphh) Do. Accordingly, (F1,.... H.,H,., \ (II,..., Jz A @ and G is guaranteed to output an example in supp(h) on round s. Since s 2 t" was chosen arbitrarily, this is true for all such s. completing the proof.
F. Proof of Lemma 3.6
Proof. Let X be countable and H. S {0, 1 be any class satisfying the UUS property. Suppose there exists a non- decreasing sequence of classes Hi C H2 C such that H = U H4 and NC,(H.) < oo for all e N. For sequence 21, .2...., let d, := [ 22 denote the number of distinct examples amongst the first t examples. Consider the following generator G. At time L E N, 9 computes j: == max E [4] NC,(HL) < de) U (0). If j. = 0, & plays any x E X. Otherwise, it plays from (#1, He)H,, J. {I1, 22......... }. We claim that G is a non-uniform deieedeependent generator for H. To see why, let n² E N and h E H be the noise level and hypothesis picked by the adversary. Let i" E N be the smallest index such that E H4s and define jr = max(i", ,n*). We claim that g perfectly generates after observing max (NC,- (H2,)) + 1,5*} distinct examples. To that end, let 31, T., . be any
14

---

Generation from Noisy Examples
sequence such that Et=1 1 (x & supp(h)) s n*. Without loss of generality, suppose there exists N such that d.- max 5- (H(-)) + 1, Observe that 1* 2 jr Fix any 2 t'. By definition of jt, it must be the case that j. j 2 n² Moreover, because js i", we also have that h E Hj.- Together, this means that h E Hz, (Z1,..., Tx. and (Z1...., H. S supp(h). Also, because d, > NC,, (Hz,) it must be the case that (TI,..., 2z) Hy, Iz) Accordingly, (fi,...., J. ( }s) * 0 and 9 is guaranteed to output an example in supp(h) on round 8. Since s 2 was chosen arbitrarily, this is true for all such s, completing the proof.
= oc.
G. Proof of Theorem 3.10
Proof. Let \' be countable and H S {0,1]* satisfy the UUS property. Suppose there exists a finite sequence of uniformly noise-independent generatable classes H1, H2,.... Hy such that H U Hg. By Theorem 3.1, we know that for all i [k], we have that NNER, supp(h) oc. For every E [b), let =i, 22, ... denote the elements of ONEN, supp(h) sorted in their natural ordering. Consider the following generator G. Given any noisy enumeration T2,,,,,.. and any / E N, 9 first computes
p = max E N: {
z// S (ZI,...,III}} r.}}
for every i [kt] Then, computes & arg [ p/. Finally, 9 plays arbitrarily from {2ft, 23 ..... (.......1)) We claim that 9 generates from H in the limit.
To see why, let h E H. and Ti, T2,... be the hypothesis and noisy enumeration selected by the adversary. Let i E [k] be such that E Mi- and s* E NN be such that for all 2 s" we have that H₁ E supp(h). Such an s* exists because
Ei= 1 (2x & supp(h)} < co. Let S* S [k] be such that S* if and only if 22......... S {x1, T2,... J. Note that E S' by definition of 2 22 ..... and the fact that 11, #2, is noisy enumeration. By definition of S* and p must be the case that for all j $ S*, we have that suPteN pi < co. Since k < oo, we then get that maxjęs+ suPteN P/ co. On the other hand, for all E S we have that pt - 0c. More precisely, for every
S there exists finite t, E N such that pi. 2 maxjes- suPten p/- Since [S*| < oo, we also have that t" == maxies- 4 < co. Our proof is complete after noting that for all 2 t", we have that in S* and {2] 2 ... \ {x1.....r)) xr} S supp(h).
15


Reviews:
[{"review_id": "yUmGIp8RDb", "reviewer": "Reviewer_uTiP", "summary": "This paper proposes an extension of the theoretical model of language generation introduced by Kleinberg & Mullainathan (2024), exploring the impact of noisy example streams on generatability. The authors introduce the concepts of \"noisy uniform generatability,\" \"noisy non-uniform generatability,\" and \"noisy generatability in the limit\" to account for the influence of noise in the example stream, addressing a significant gap in previous research which assumed a noiseless setting. Key contributions include a complete characterization of noisy uniform generatability through the Noisy Closure dimension, new conditions for noisy non-uniform generatability, and sufficient conditions for noisy generatability in the limit. The paper also demonstrates that while noisy uniform generation is more difficult than its noiseless counterpart, all finite classes are still noisily uniformly generatable.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We address their questions and concerns below. \n\n> However, what are the technical difficulties and contributions, especially given that noise has already been extensively studied in non-generative contexts?\n\nAs the reviewer noted, noise has been extensively studied in non-generative contexts, for example in PAC and online learnability. However, to the best of our knowledge, this is the first work to rigorously formalize and study noise in the framework posed by Kleinberg \\& Mullainathan (2024) and Li. et al. (2024). Our main contributions are summarized near the end of Section 1. At a high level:\n\n1) We introduce a learning-theoretic theoretical framework for studying noise in language generation,\n2) We provide necessary and sufficient conditions in terms of combinatorial dimensions for various notions of noisy generation, spanning different levels of difficulty for the generator.\n\nWe feel that this work is an important stepping stone towards bridging learning theory and robustness in generative machine learning. As for technical difficulties, accounting for noise in the data stream requires new proof techniques. Indeed, since, in our model of noise, the generator does not know the number or location of noisy examples, it is a priori unclear whether and how generation of clean positive examples is possible. Nevertheless, it is possible, and our results show that indeed we need to go beyond existing results by considering scale-sensitive dimensions. This is unlike in prediction, where one does not need a scale-sensitive dimension to characterize agnostic PAC and online learnability.\n\n> While this paper is theoretical and does not require experimental validation, would it be possible to conduct experiments? If so, how could one design and organize such experiments?\n\nThis is a great question, and one that we have been thinking about too! One high-level takeaway from our results is that in order to be robust to noisy examples in the training data, one needs to explicitly incorporate the fact that noisy data may be present in the training dataset during the process of training a generator. Moreover, our results hint at the fact that it might be useful to iteratively guess the level of noise in the training data and use this guess to adapt the training procedure. These two insights may lead to the following generation algorithm which could be interesting to study experimentally: start with an initial guess of the noise in the training set, use this initial guess to train a robust variant of a GAN that can take in a noise-level, use the robust GAN to estimate the amount of noise in the training data, and repeat this process. \n\n> There appears to be a typo on line 63—should \"positive examples\" be \"negative examples\"?\n\nThe reviewer is exactly right! This should be negative examples. We will make sure to fix this in the final version.", "claims_and_evidence": "1. The paper extends Kleinberg & Mullainathan’s (2024) theoretical framework to include the impact of noisy example streams on generatability. Compared to the conclusions in noiseless settings, the new findings under noisy conditions are indeed a significant contribution. However, what are the technical difficulties and contributions, especially given that noise has already been extensively studied in non-generative contexts?\n2. While this paper is theoretical and does not require experimental validation, would it be possible to conduct experiments? If so, how could one design and organize such experiments?\n3. There appears to be a typo on line 63—should \"positive examples\" be \"negative examples\"?", "methods_and_evaluation_criteria": "The exploration of conclusions under noisy conditions is relevant and meaningful.", "theoretical_claims": "The theory appears to be sound.", "experimental_designs_or_analyses": "See the second point in Claims And Evidence", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K5fwgXoWeu", "reviewer": "Reviewer_do42", "summary": "The paper extends prior work on language generation by studying the generation of new, unseen positive examples even when the example stream is adversarially contaminated with a finite number of noisy (negative) examples.\nIt introduces new notions, namely noisy uniform generatability, noisy non-uniform generatability, and noisy generatability in the limit; these notions adapt the already introduced framework of uniform and non-uniform generation (as well as generation in the limit) to more realistic, noisy settings.\nThe authors also introduce the setting of uniform noisy generation, but prove that it is a significantly harder problem in that even hypothesis classes with just two hypotheses might not be uniformly noisily generatable.\nA key contribution is the introduction of the Noisy Closure dimension, a scale-sensitive dimension that extends the Closure dimension (Li et al., 2024) and characterizes when a hypothesis class can be noisily generated, providing some sufficient and necessary conditions.\nThe authors further demonstrate that all countable classes are noisily non-uniformly generatable, ensuring they can eventually generate new positive examples even under finite noise in the stream.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions. We agree with all the suggestions made by the reviewer and will make sure to incorporate these along with fixing the typos in the camera-ready version. Below, we address some questions and concerns. \n\n> More precisely, there is a wrong choice of indices in the proof of Theorem 3.9, as it seems that authors mistakenly swapped  with  starting from line 425. One would then need to fix this and verify whether the following claims still hold true.\n\nWe thank the reviewer for catching this typo! The reviewer is exactly correct, and the claim goes through with this modification. We will make sure to make this change in the camera-ready version.\n\n> Additionally, in the proof of Theorem 3.1, the authors claim that...\n\nWe thank the reviewer for this comment. However, we do believe that $x_1, \\dots, x_d, z_1, \\dots, z_d$ contains $2d$ points. To see why, suppose that $x_1, \\dots, x_d$ is any set of $d$ distinct points in $\\bigcap_{h \\in F\\setminus \\{f\\}} \\operatorname{supp}(h).$ It suffices to show that $\\{x_1, \\dots, x_d\\}$ and $\\operatorname{supp}(f) \\setminus \\bigcap_{h \\in F} \\operatorname{supp}(h)$ are disjoint. Pick some $x_i \\in \\lbrace\\{x_1, \\dots, x_d\\rbrace\\}$. If $x_i \\in \\operatorname{supp}(f)$, then $x_i \\in \\bigcap_{h \\in F} \\operatorname{supp}(h)$. To see why, recall that $x_i \\in \\bigcap_{h \\in F\\setminus \\{f\\}} \\operatorname{supp}(h)$ which means that $x_i \\in \\operatorname{supp}(h)$ for all $h \\in  F\\setminus \\{f\\}$. Thus, if $x_i $ is also in $\\operatorname{supp}(f)$, then it must be the case that $x_i \\in \\bigcap_{h \\in F} \\operatorname{supp}(h)$. Overall, this means that $x_i \\notin \\operatorname{supp}(f) \\setminus \\bigcap_{h \\in F} \\operatorname{supp}(h).$ On the other hand, if $x_i \\notin \\operatorname{supp}(f)$, then it must be the case that $x_i \\notin \\operatorname{supp}(f) \\setminus \\bigcap_{h \\in F} \\operatorname{supp}(h),$ completing the proof.  We will make sure to clarify this in the camera ready version. \n\n> Do you believe it is possible to extend this generation framework beyond the \"binary classification\" one?\n\nYes, we do believe that these results should generalize to the multiclass case through the similar setup of prompted generation from Li et al. (2024). For finite label spaces, the characterization of noisy generatability should remain unchanged and simply requires modifying the noisy closure dimension into the prompted noisy closure dimension. However, the more interesting case of infinite labels is unclear. We think this is an interesting direction of future work!\n\n> Do you think the framework could be extended further, other than the multiclass one mentioned above? Do you foresee any technical challenge that would require significant changes in the framework or in the assumptions made?\n\nYes, we believe there are several frameworks for modeling noise that are of interest, beyond the multi class case and the setting we considered. For example,  one could also consider noisy generation in a stochastic setting like that studied by Kalavasis et a. [2024]. Moreover, one can also study variants of the noisy model where, for example, the injection of noise must follow a particular rate or where the generator has query access whether an example is noisy or not. In general, in the real-world, data is most likely not worst-case, and additional feedback is often available to the generator. Thus, it is an interesting direction to study relaxations of our model by either weakening the adversary or strengthening the generator. New techniques will need to be developed to understand how much such relaxations can help. \n\nKalavasis, Alkis, Anay Mehrotra, and Grigoris Velegkas. \"On the limits of language generation: Trade-offs between hallucination and mode collapse.\" arXiv preprint arXiv:2411.09642 (2024).", "claims_and_evidence": "The claims are clearly stated and supported by sufficient evidence.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Overall, the proofs of the claims are mainly correct.\nSome parts, however, contain some mistakes that would need some adjustment.\nMore precisely, there is a wrong choice of indices in the proof of Theorem 3.9, as it seems that authors mistakenly swapped $s$ with $t$ starting from line 425.\nOne would then need to fix this and verify whether the following claims still hold true.\nAdditionally, in the proof of Theorem 3.1, the authors claim that $x\\_1, \\\\dots, x\\_d, z\\_1, \\\\dots, z\\_d$ contain $2d$ unique examples (lines 248 and 269) while this is not necessarily true, i.e., there can exist $i,j \\\\in \\[d\\]$ such that $x\\_i = z\\_j$.\nThis would require a different selection of those $2d$ examples in order to ensure their uniqueness.\nAnyways, these are not major issues and they appear to be fixable at first glance.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "I believe the main contributions of this work nicely extend the already available results on models for (language) generation to a more realistic setting with adversarial noise in the example stream.\nAs already remarkes, the authors do a good job in comparing to existing results and clearly framing their contribution relative to them.", "essential_references_not_discussed": "The authors discussed the most relevant literature.", "other_strengths_and_weaknesses": "A formal framework for the study of (language) generation was already introduced, as outlined by the authors themselves.\nNevertheless, handling the presence of noise in the stream is quite interesting and requires an adaptation of ideas from previous work, without being a direct consequence of them.\nThe authors also cover multiple settings where the difference lies in the dependence of the number of mistakes on the noise level and the hypothesis used to generate the positive examples, and extensively study their differences.", "other_comments_or_suggestions": "- The function $\\\\mathrm{supp}(\\\\cdot)$ is used but never formally defined. It would be better to have a definition, e.g., $\\\\mathrm{supp}(h) = h^{-1}(1)$.\n- In the definition of $\\\\mathcal{H}(x\\_{1:d},n)$ it would be better to use a semicolon (or a pipe) to separate examples from noise level, as it makes it easier to parse $\\\\mathcal{H}(x\\_1, \\\\dots, x\\_d; n)$ (see preliminaries and, e.g., line 345)\n- Please, specify that you assume the natural numbers $\\\\mathbb{N}$ consist of the positive integers (excluding $0$), since it is not a universal assumption.\n- At line 326, it could also be helpful to add the \"mistake bound\" from online learning as another helpful analogy other than the \"sample complexity\".\n- Maybe specify that the assumption at line 356 in the proof of Lemma 3.8 is without loss of generality if that is the case.\n- It seems that the inner loop of Algorithm 1 might always stop withing one of its iterations, and so the last line might be superfluous. For instance, in the proof of Theorem 3.9 at lines 385-392, the case $j = r\\_s+1$ might contradict the properties of $\\\\mathcal{Q}$ since it is always given $x\\_{r\\_s}$ as input when generating $\\\\hat z\\_1^s, \\\\dots, \\\\hat z\\_{r\\_s}^s$; hence, the if condition within the inner loops should be true for at least one $i \\\\in \\[r\\_s\\]$.\n\nTypos:\n- Line 14: \"by\" instead of \"by the\".\n- Line 62: \"negative\" instead of \"positive\".\n- Line 91: \"a countably\" instead of \"an countably\".\n- Line 122: \"is possible\" instead of \"possible\".\n- Line 179: \"countably infinite\" instead of \"countable infinite\".\n- Lines 182-183 should go at the beginning of Section 2, since the notation is already used before.\n- Line 168: $\\\\in \\\\mathrm{supp}(h)$ instead of $\\\\subseteq \\\\mathrm{supp}(h)$, or put curly brackets around sequence.\n- Line 202: \"as a stream\" instead of \"of stream\".\n- Line 204: missing period at the end.\n- Lines 190-197: $d^*$ instead of $d$ to be consistent with Definition 2.4.\n- Line 228: \"form\" instead of \"from\".\n- Lines 234-235: \"any subset\" instead of \"the any subset\", \"for which there exists\" instead of \"there exists\", $\\\\mathcal{F}\\\\setminus\\\\{f\\\\}$ instead of $\\\\mathcal{F}\\\\setminus f$.\n- Line 245: $\\\\mathcal{F}\\\\setminus\\\\{f\\\\}$ instead of $\\\\mathcal{F}\\\\setminus f$.\n- Line 287: \"noise level\" instead of \"level\" for clarity.\n- Line 288: \"exist\" instead of \"exists\".\n- Line 294: \"as it is defined\" instead of \"it is defined\".\n- Line 312: $h \\\\in \\\\mathcal{H}$ instead of $h \\\\in \\\\mathrm{supp}(h)$.\n- Line 319: \"being\" instead of \"bring\".\n- Line 291: specify \"positive examples\".\n- Line 295: \"a subset of $\\\\mathcal{H}$\" should refer more precisely to $\\\\mathcal{F}$.\n- Line 338: specify Corollary 3.4 other than Theorem 3.3 for the result to follow.\n- Line 381: \"countable\" instead of \"countably infinite\".\n- Line 420: \"at most\" instead of \"most\".\n- Lines 425-439, left column: all references to $t$ should actually be $s$, given line 423.\n- Lines 385-392, right column: all references to $t$ should actually be $s$, given line 423.\n- Line 397: \"another\" instead of \"a another\".", "questions_for_authors": "- Do you believe it is possible to extend this generation framework beyond the \"binary classification\" one? For instance, consider generating a sequence with examples belonging to multiple classes and guaranteeing the generation of examples from some of these classes.\n- Do you think the framework could be extended further, other than the multiclass one mentioned above? Do you foresee any technical challenge that would require significant changes in the framework or in the assumptions made?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gxBZcxI2u4", "reviewer": "Reviewer_Us4m", "summary": "The paper studies the problem of language generation in the limit in a noisy setting where an adversary inserts a finite number of negative examples. The paper provides necessary and sufficient conditions for when a binary hypothesis class can be noisily generatable. The paper examines various definitions of noisy generatability.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "The proofs in the main text appear to be correct.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper extends the previous work by Kleinberg & Mullainathan (2024) to the noisy examples setting.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "1. The paper is well-written with nice intuition, and the math is rigorous.\n2. The paper provides a complete characterization of which classes are noisily uniformly generatable.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0FMi1zQeot", "reviewer": "Reviewer_gxU2", "summary": "This paper studies the model of language generation in the limit, first introduced by Kleinberg and Mulainathan at NeurIPS 2024 and later extended by Lee et al. It builds on seminal work by Gould and Angwin from the 1960s, which has had a profound influence on learning theory. The study this language generation model is nascent and has several open problems. This work tackles a fundamental open problem: learning from adversarially injected noise. Specifically, the authors consider a scenario in which an adversary inserts a finite number of incorrect examples into the learner’s data stream.\n\nThe paper defines several models of language generation that mirror the three frameworks proposed by Lee et al.: uniform generation, non-uniform generation, and generation. Additionally, the authors introduce two further models that require the learner’s number of mistakes to be independent of the noise level. For the primary three models, they characterize conditions under which uniform and non-uniform generation can be achieved in a noisy setting and provide several sufficient conditions for generation with noisy examples. Notably, these conditions demonstrate that noisy generation is feasible for all countable collections – a result that strengthens the stark contrast between language identification and language generation, showing that the latter remains possible even in the presence of adversarial corruptions.\n\nThe paper’s results are primarily existential or non-computational, relying on the existence of certain oracles. The authors leave open the challenge of extending these findings to computable or algorithmic results and also leave the complete characterization of generation with noisy examples to future work.\n\n## Update after the rebuttal\nI thank the reviewer's for explaining their fix to Theorem 3.1. I maintain my original rating.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. We will make sure to address all typos (i.e., typos 1-7) and suggestions (i.e., suggestions 1-5) in the camera-ready version. \n\n> Could you please confirm if the issue I mentioned in the proof of Theorem 3.1 is correct, and could you check whether it could be fixed?\n\nWe thank the reviewer for catching this bug! We agree with the reviewer's finding that our proof of Theorem 3.1 is incomplete since there exists classes $F$ such that $|\\bigcap_{h \\in F} \\operatorname{supp}(h)| < \\infty$, but for every $f \\in F$, we still have that  $|\\bigcap_{h \\in F\\setminus \\{f\\}} \\operatorname{supp}(h)| < \\infty$ (e.g. the example provided by the reviewer). However, the reviewer's fix to the proof of the necessity direction does *not* work, and the class they provided shows that the condition is Theorem 3.1 is *not* necessary.\n\nThe reason is subtle and due to the fact that in Definition 2.4 (line 186-187), we decided to measure the \"sample complexity\" of the generator in terms of the number *positive* examples it has seen and not the *overall* number of unique examples, since the latter is too stringent (as evidenced by the reviewer's own proof). That is, as written in Definition 2.4 , the generator only needs to be correct after observing $d$ *positive* examples. This is unlike our definitions for noisy uniform, noisy non-uniform, and in-the-limit, where the \"sample complexity\" is defined with respect to the *total number* of examples (i.e the generator has to be correct after observing any $d$ examples). We agree this is confusing and we will change Definition 2.4 so that it matches the definitions for noisy uniform, noisy non-uniform, and in-the-limit. After doing so, the reviewer's necessity proof is now correct and the characterization in Theorem 3.1 holds for the modified version of uniform noisy generatability where we measure the sample complexity in terms of the *total number* of examples. We will make a note of this in the camera-ready version and acknowledge the reviewer for their contribution. \n\nNevertheless, the current proof of the necessity direction of Theorem 3.1 gives the following necessary condition for Definition 2.4 as it is written: if there exists a subclass $F\\subseteq  H$ and hypothesis $f \\in F$ such that $|\\bigcap_{h \\in F} \\operatorname{supp}(h)| < \\infty$ and $|\\bigcap_{h \\in F\\setminus \\{f\\}} \\operatorname{supp}(h)| = \\infty$, then $F$ is not uniformly noisily generatable when the sample complexity is measured in terms of positive examples. Note that all finite classes whose closure is finite satisfy this property. **Thus, the main takeaway of the section remains unchanged  -- uniform noisy generation is hard and only possible for finite classes that are generatable immediately.** We will correct Theorem 3.1 appropriately. \n\nThe reviewer's counterexample highlights an interesting separation in generatability based on whether one measures the sample complexity in terms of only the positive examples or all examples. For completeness sake, we can \"fix\" Theorem 3.1  by providing a new characterization of uniformly noisy generatability when the sample complexity measures only the positive examples, like what is currently written in Definition 2.4.  \n\nClaim: A class $H$ is uniformly noisily generatable if and only if $\\sup_n (NC_n(H) - n) < \\infty$. \n\nProof sketch: For the necessity direction, suppose that $\\sup_n (NC_n(H) - n) = \\infty$. Then for every $d \\in \\mathbb{N}$, we can find a $t \\geq d$ and a sequence $x_1, \\dots, x_t$, such that $|\\langle x_1, ..., x_t \\rangle_{H, t-d}| < \\infty.$ Hence, by padding $x_1, \\dots, x_t$ with any remaining elements in $\\langle x_1, ..., x_t \\rangle_{H, t-d}$, we can force the Generator to make a mistake while ensuring that the hypothesis chosen is consistent with at least $d$ examples in the stream. For the sufficiency direction, if  $\\sup_n (NC_n(H) - n) < \\infty$, then there exists a $d \\in \\mathbb{N}$ such that for every $t \\geq d$ and distinct $x_1, ..., x_t$, we have that either $\\langle x_1, ..., x_t \\rangle_{H, t-d} = \\bot$ or $|\\langle x_1, ..., x_t \\rangle_{H, t-d}| = \\infty.$ Thus, the algorithm which for $t \\geq d$ plays from $\\langle x_1, ..., x_t \\rangle_{H, t-d}\\setminus \\lbrace{x_1, \\dots, x_{t}\\rbrace}$ if $\\langle x_1, ..., x_t \\rangle_{H, t-d} \\neq \\bot$ is guaranteed to succeed.\n\nTo put this into context, if one measures sample complexity with respect to the *overall* number of examples, then another characterization of uniform noisy generatability is the finiteness of $\\sup_n (NC_n(H))$. Thus, the difference between measuring the sample complexity with respect to just positive examples or with respect to all samples is whether or not you subtract $n$ from $NC_n(H)$.", "claims_and_evidence": "The paper’s claims are generally well-supported by formal proofs, and overall, I find the arguments convincing and plausible. However, I have some reservations regarding the proof of Theorem 3.1. The proof begins by considering a set F such that the common intersection of all hypotheses in F is finite, and that there exists at least one hypothesis in F whose removal renders the common support infinite. I am not entirely convinced that such a collection F necessarily exists in all cases. For instance, consider the hypothesis class $H = \\\\{\\mathbb{Z}_{\\geq i} \\cup \\\\{\\infty\\\\}\\mid i\\in \\mathbb{N}\\\\}$. \n\nA potential fix for the proof could be as follows: First, exhaust the common intersection of H, which is finite by definition. Then, regardless of the uniform bound d, consider the time d+C, where C is the size of the common intersection. Two cases arise: if the learner outputs an element from the common intersection, it must be a mistake since that element appears in the training set; if not, there exists some hypothesis h that does not include the learner’s output. In this scenario, one can select this h as the target hypothesis and treat all outputs prior to it (except those in the common intersection) as noise.", "methods_and_evaluation_criteria": "Not applicable", "theoretical_claims": "I did not carefully check the proofs of the theorems but I did sanity check that the results sound plausible based on the existing results on language generation.", "experimental_designs_or_analyses": "Not applicable", "relation_to_broader_scientific_literature": "**Novelty compared to existing works**\nAs the authors agree, the results and techniques of this paper are similar to those of Li et al. For example, the definition of the noisy closure dimension is clean but is a simple (but not immediately obvious) extension of the closure dimension introduced by Li et al. While the definitions and proof structures are similar, I think there are enough differences to justify accepting this paper to ICML. Further, the paper studies a foundational problem that is fundamentally different from the problem studied in Li et al. The fact that the characterizations end up being similar in spirit as those of Li et al. should not be considered a weakness of this paper but rather a strength. \n\n**Comparison to Related Work**\nI think the paper does a good job of discussing recent related works and mentioning the related works on language identification in the noisy setting. To further improve the writing, it would be useful to compare the results in this paper to existing results on language identification with noise from earlier studies. Given space constraints, this discussion could be in an appendix; but it would be very useful for the reader to see a summary of the results from prior work", "essential_references_not_discussed": "Not applicable", "other_strengths_and_weaknesses": "This paper is very relevant to the ICML community and one of its strengths is that it tackles a fundamental problem in the foundations of generative AI; using a recent model of language generation.", "other_comments_or_suggestions": "Suggestions to improve writing \n1. Li et al. leave the complete characterization of generation in the limit open, and while this is not immediately relevant to the work, it would be useful to highlight this in the related works for the benefit of the reader. The authors do mention this in section 4 of discussion and open questions, but I believe it also belongs in the related work.\n2. In addition, the naming of Assumption 2.1 seems unnecessarily complex. instead of writing it this way, one could for instance, say “Let $H$ be any hypothesis class consisting of infinite hypothesis”\n3. The names of Definitions 2.4 and 2.5 are also somewhat confusing and difficult to distinguish. I strongly suggest renaming them to more descriptive terms like “noise level independent uniform generatability” and “noise level dependent uniform generatability.”\n4. Moreover, the paper alternates between interpreting hypotheses as functions and as sets. It would be helpful for the reader to be consistent about how hypotheses are interpreted as functions or as sets.\n5. Finally, given the number of interesting results, it would be very useful to include a diagram that summarizes the different notions of generation (both with and without noise) along with their corresponding dimensions. Arrows illustrating the implications between these concepts.\n\n\nTypos\n\n1. Line 13 Column 2: Li ⊂ U should have ⊆? And in other pleases also, e.g., in related work  \n2. In Line 66 Column 1, the citations should be either chronological or alphabetical? Currently, they seem to follow neither ordering.  \n3. Line 81 column 2 typo repeated “in terms”  \n4. Line 155 column 2, has a typo, one needs to consider the size of the set (to be less than ∞). The same issue is also present in other places, e.g., Definitions 2.4 and 2.5.  \n5. The notation “abbreviate a finite sequence x1, . . . , xn as x1:n.”  from line 183 should appear earlier in the preliminaries – before its first use.  \n6. Line 324 column 1, Line 347 column 1 etc. have some typos – which seem like a missing latex definition.  \n7. Some citations have “et al.” please present full citations", "questions_for_authors": "Q1. Could you please confirm if the issue I mentioned in the proof of Theorem 3.1 is correct, and could you check whether it could be fixed?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "Not applicable"}}]

Author rebuttal:

Meta-review: This work studies language generation (generation of new, unseen positive examples) in the presence of adversarial contamination with negative examples. A systematic investigation of this task is initiated and a characterization is given under some conditions. The reviewers agreed that this is an interesting contribution that merits acceptance.
Decision: Accept (poster)