Generation from Noisy Examples

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.

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?

We 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.

The 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.

Nevertheless, 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.

The 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.

Claim: A class $H$ is uniformly noisily generatable if and only if $\sup_n (NC_n(H) - n) < \infty$.

Proof 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.

To 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)$.

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.

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.

We 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.

Additionally, in the proof of Theorem 3.1, the authors claim that...

We 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.

Do you believe it is possible to extend this generation framework beyond the "binary classification" one?

Yes, 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!

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?

Yes, 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.

Kalavasis, 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).

We thank the reviewer for their comments. We address their questions and concerns below.

However, what are the technical difficulties and contributions, especially given that noise has already been extensively studied in non-generative contexts?

As 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:

1. We introduce a learning-theoretic theoretical framework for studying noise in language generation,
2. 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.

We 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.

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?

This 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.

There appears to be a typo on line 63—should "positive examples" be "negative examples"?

The reviewer is exactly right! This should be negative examples. We will make sure to fix this in the final version.