arXiv CSopen access

Differentially Private Language Generation and Identification in the Limit

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

machine learning, deep learning, neural networks

arXiv:2604.08504v1 [stat.ML] 9 Apr 2026

Differentially Private Language Generation and Identification in the Limit Anay Mehrotra Stanford University [email protected]

Grigoris Velegkas Google Research [email protected]

Xifan Yu Yale University [email protected]

Felix Zhou Yale University [email protected]

Abstract We initiate the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan [KM24], under the constraint of differential privacy. We consider the continual release model, where a generator must eventually output a stream of valid strings while protecting the privacy of the entire input sequence. Our first main result is that for countable collections of languages, privacy comes at no qualitative cost: we provide an εdifferentially-private algorithm that generates in the limit from any countable collection. This stands in contrast to many learning settings where privacy renders learnability impossible. However, privacy does impose a quantitative cost: there are finite collections of size k for which uniform private generation requires Ω(k/ε) samples, whereas just one sample suffices non-privately. We then turn to the harder problem of language identification in the limit. Here, we show that privacy creates fundamental barriers. We prove that no ε-DP algorithm can identify a collection containing two languages with an infinite intersection and a finite set difference, a condition far stronger than the classical non-private characterization of identification. Next, we turn to the stochastic setting where the sample strings are sampled i.i.d. from a distribution (instead of being generated by an adversary). Here, we show that private identification is possible if and only if the collection is identifiable in the adversarial model. Together, our results establish new dimensions along which generation and identification differ and, for identification, a separation between adversarial and stochastic settings induced by privacy constraints.

Contents 1

Introduction 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2 4

Technical Overview 2.1 Online Model of Private Identification (Theorem 1.5 and Theorem C.5) . . . . . . . . 2.2 Stochastic Model of Private Identification (Theorem 1.6) . . . . . . . . . . . . . . . . . 2.3 Private Generation (Theorem 1.1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Sample Complexity of Private Generation (Theorems 1.2 and 1.3) . . . . . . . . . . .

5 5 5 6 7

Model and Preliminaries 8 3.1 Language Generation and Identification in the Limit . . . . . . . . . . . . . . . . . . . 8 3.2 Differential Privacy and Continual Release . . . . . . . . . . . . . . . . . . . . . . . . 10

Proofs of Theorems 1.1 and 1.5 4.1 Proof of Theorem 1.1 (Private Generation for Countable Collections) . . . . . . . . . 4.1.1 Non-Uniform Generation Guarantee . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Proof of Theorem 1.5 (Private Online Identification Lower Bound) . . . . . . . . . . .

10 10 13 13

Conclusion

A Additional Preliminaries A.1 Characterization of Language Identification in the Limit . . . . . . . . . . . . . . . . A.2 Stochastic Identification in the Limit . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Borel–Cantelli Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.4 Privacy Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22 22 22 23 23

B Additional Related Work

C Deferred Proofs C.1 Proof of Theorem 1.2 (Upper Bound on Sample Complexity) . . . . . . . . . . . . . . C.2 Proof of Theorem 1.3 (Lower Bound on Sample Complexity) . . . . . . . . . . . . . . C.3 Proof of Theorem C.5 (Private Online Identification Upper Bound) . . . . . . . . . . C.4 Proof of Theorem 1.6 (Private Stochastic Identification) . . . . . . . . . . . . . . . . .

24 24 28 31 33

Introduction

Machine learning systems are increasingly trained on sensitive data. Once deployed, a model can be queried, shared, and repurposed in ways that may expose information about individual training records. This necessitates systems that are trained with privacy guarantees which remain meaningful both in the presence of public information held by a malicious adversary and downstream post-processing. Differential privacy (DP) [DMNS06] has become the standard formalization of this requirement. DP is a stability guarantee for randomized algorithms: informally, it requires that changing a single user record in the training data does not significantly change the distribution over outputs. DP has been studied extensively in both practice and theory, and a recurring theme is a privacy–utility trade-off. For example, in private PAC learning, pure DP has been investigated in a long line of work (see, e.g., [KLNR+11; ALMM19; BLM20; GGKM21; BBDS+24; FHMS+24; HMST25]), revealing several regimes where privacy requires additional samples or even renders learning impossible compared to the non-private setting. For instance, the task of PAC learning simple classes such as one-dimensional thresholds with approximate DP guarantees is already infeasible [ALMM19]. The recent success of large language models (LLMs) at language generation has brought these questions to the foreground. Their training relies on vast text corpora that may contain sensitive data, and interactive querying has been shown to elicit memorized fragments [CTWJ+21]. This has led to growing interest in training and adapting language models with formal privacy guarantees, including DP pretraining and fine-tuning efforts (see, e.g., [MRTZ18; LTLH22; YNBG+24; SMML+25; ZZME+25]). These developments motivate a mathematical study of language generation under differential privacy. We study this question within the recent model of language generation in the limit introduced by Kleinberg and Mullainathan [KM24]. This model is motivated by classical adversarial frameworks for learning and identification [Gol67; Lit88], but it replaces the goal of exact identification with the goal of generation – producing valid unseen strings from the underlying language. The process begins with an adversary selecting a target language K from a known collection L = { L1 , L2 , . . . } and fixing an enumeration of K.1 At each step n ≥ 1, the adversary reveals the n-th element xn of the enumeration. Having observed the set of examples Sn = { x1 , . . . , xn }, the generator G must output a new string wn ∈ / Sn intended to be a valid, unseen element of K. A generator G is said to be successful if it learns to generate from L in the limit: for any K ∈ L and any enumeration of K, there exists a finite round n⋆ such that for all n ≥ n⋆ , the output is always correct and novel, wn ∈ K \ Sn . This framework is rooted in Gold’s notion of identification in the limit [Gol67], which requires the learner to identify the target language exactly. While identification is impossible for most nontrivial language collections, [KM24] showed that the weaker objective of generation is feasible in striking generality, including for any countable collection of languages. This separation has catalyzed a wave of recent work refining the model and its guarantees (e.g., [CP25; KMV25; LRT25; RR25]); see Section 1.2. Given this context, we investigate the possibility of language generation under differential privacy. 1 Formally, an enumeration of K is an infinite sequence x , x , . . . (potentially with duplicates) such that x ∈ K for all 1 2 i i and every x ∈ K appears at some index.

To study privacy in this setting, it is not enough to protect a single output of the generator. Language generation is an ongoing interaction: after observing x1:n the generator outputs wn , and the privacy guarantee should apply to the entire transcript of outputs. Accordingly, we adopt the continual release model of DP [DNPR10; CSS11], which (informally) requires that for any two input streams that differ at exactly one timestep, the joint distribution of the entire output stream changes by at most a multiplicative factor of eε (for desired privacy value ε > 0). This temporal requirement is strictly stronger than one-shot privacy, and even for simple tasks, it is known to induce error that grows with the length of the stream [JRSS23; CLNS+24; ELMZ25]. In our setting, this challenge is compounded by the fact that the number of rounds until convergence is not known in advance and the stream length is infinite. This brings us to the main question studied in this work: Q: Which collections L are generatable in the limit under ε-DP in the continual release model? As any non-trivial DP algorithm is necessarily randomized, we allow failures on probability 0 events.

1.1

Our Contributions

Our first result shows that ε-DP language generation is possible for all countable collections. Theorem 1.1 (Private Generation). For any ε > 0, there is an algorithm G (Algorithm 1) that, for any countable collection L , G is ε-DP in the continual release model and generates in the limit from L . Thus, requiring differential privacy even in the stronger continual release model does not make the problem of generation harder, and it remains possible for all countable collections. This stands in contrast to many other learning tasks, where imposing differential privacy often introduces a fundamental privacy–utility trade-off. At this level of generality (only requiring generation in the limit), privacy appears to come for “free” for language generation. We revisit this observation when we consider sample complexity below. While the above algorithm is able to generate in the limit, the time step n⋆ after which it begins generating correctly depends, in general, on the choice of the target language K. For finite collections, we can avoid this: the next result provides a uniform bound on the number of samples required for generation in the limit, independent of the choice of the target language and its enumeration. In the non-private setting, [KM24] showed that if L has finite size, then n⋆ (the time at which the generator starts generating correctly) can be upper bounded by a quantity n(L ) that only depends on the collection L and not on the target language K or the adversary’s enumeration. Furthermore, Li, Raman, and Tewari [LRT25] characterized the time n⋆ exactly using the notion of closure dimension, defined later on in Definition 2, which is analogous to how the Littlestone dimension characterizes the mistake bound in online learning. For a language collection L of closure dimension d, [LRT25] showed that seeing n⋆ = d + 1 distinct input elements is both necessary and sufficient for uniform generation from L . Our Theorem 1.2 provides an analogous guarantee in the private setting, which says that if we desire a probability 1 − β of “success” by time n⋆ , then e ((k/ε) · log(1/β)). the analogous quantity for us is n⋆ = d + O 2

Theorem 1.2 (Sample-Complexity Upper Bound; Informal; see Theorem C.1). There is an ε-DP continual release algorithm G that generates from any finite collection L of size k and closure dimene ((k/ε) log (1/β)) sion d. For any β > 0, the step n⋆ after which G generates satisfies n⋆ ≤ d + O with probability 1 − β. Note that the bound on n⋆ is independent of the target language and its enumeration. The sample complexity’s dependence on d is expected as it also arises without requiring privacy. Further, the dependence on k/ε in the sample complexity of Theorem 1.2 is almost tight: k/ε samples are required to achieve even a success probability of 2/3, as shown in our next result. Theorem 1.3 (Sample-Complexity Lower Bound; Informal; see Theorem C.3). For any k, d ∈ N, there is a finite collection L of size k with closure dimension d such that if the time step n⋆ after which an ε-DP generation algorithm in the continual release model uniformly generates from L satisfies n⋆ ≤ m with probability at least 2/3 independent of the target language and its enumeration, then m = d + Ω (k/ε). Moreover, in the absence of privacy constraints, there is an algorithm that generates after observing d + 1 elements from the adversary. This shows that the dependence on d + k/ε is unavoidable for uniform private generation (in the sense of Theorem 1.2). In fact, we prove a stronger lower bound that already applies under oneshot ε-DP at a single time step (without assuming the stronger continual release requirement). Thus, for uniform generation from finite collections, there is a privacy–utility trade-off: without privacy, generation can succeed after just d + 1 samples, whereas with privacy, d + Θ(k/ε) samples are necessary. This gap can be made arbitrarily large by increasing the size of the collection k (while keeping d fixed). Remark 1.4 (Non-Uniform Generation). The algorithm in Theorem 1.1 achieves a stronger guarantee of non-uniform generation [LRT25] (see Remark 4.2). Private identification. Since requiring differential privacy for generation does not restrict which collections are generatable, it is natural to ask whether the same is true for language identification in the limit, as defined by Gold [Gol67]. In this model, an adversary similarly selects a target language K = Li⋆ from a known collection L = { L1 , L2 , . . . } and fixes an enumeration of K. The only difference is that after the adversary reveals the n-th element, the algorithm is required to output an index in . The algorithm identifies from L in the limit if there is a finite round n⋆ such that for all n ≥ n⋆ , in = i⋆ . Our next result shows that under ε-DP, unlike generation, identification becomes much harder to achieve. As before, we allow the identification algorithm to fail on an event of probability 0. Theorem 1.5 (Private Identification Barrier). If L contains two distinct Li , L j such that Li ∩ L j = ∞, Li \ L j < ∞, then no ε-DP continual release algorithm (for any ε > 0) can identify L in the limit. In particular, if L contains two languages with Li ⊆ L j , private identification is impossible. Due to this, the above condition turns out to be much stronger than Angluin’s condition (Definition 6), which characterizes non-private identification. Hence, combined with Theorem 1.1, this yields another separation between identification and generation. We complement this negative result 3

with an algorithm for collections satisfying conditions close to the negation of the above (see Theorem C.5). Finally, we study identification in the stochastic model of [Ang88], where the input stream is drawn i.i.d. from a distribution supported on the target language. Without privacy, identifiability in the stochastic and adversarial settings coincide and are characterized by Angluin’s condition (Definition 6). We show this equivalence persists under privacy. Theorem 1.6 (Private Identification in Stochastic Setting). A countable collection of languages L is privately identifiable in the limit under stochastic inputs if and only if it satisfies Angluin’s condition. Together with Theorem 1.5, this reveals a separation between adversarial and stochastic identification induced by privacy; a phenomenon absent in the non-private setting [Ang88; CPT25; KMV25] that may merit further exploration. Remark 1.7 (Statistical Rates of Private Generation and Identification). Our results and techniques have natural implications for the statistical setting studied by Kalavasis, Mehrotra, and Velegkas [KMV25] (who, in turn, use the universal rates model by Bousquet, Hanneke, Moran, van Handel, and Yehudayoff [BHMv+21]). In this setting, the algorithm receives an i.i.d. sample of size n from a distribution supported D on some language K ∈ L and its goal is to generate samples from K or, in the case of identification, identify K. For generation (respectively identification), the quantity of interest is the probability that the algorithm does not generate from K (respectively identify K) as a function of n. If this failure probability decays as C · R(c · n), we say that L is generatable (respectively identifiable) at rate R. Notably, the constants can depend on the distribution and on ε but not the target language K ∈ L . Informally, we can show that every countable collection (respectively every collection that satisfies Angluin’s condition [Ang80]) is generatable (respectively identifiable) in the limit at an (almost) exponential rate, where the constants depend on the privacy parameter ε. Such transformations from algorithms that succeed in the online setting to algorithms that achieve (almost) exponential rates have also appeared in prior works (e.g., [CPT25; KMV25; KMV26]) and our extensions utilize similar techniques.

1.2

Related Works

Our contributions draw on two main lines of work: (1) language generation in the limit, and (2) differential privacy under continual release. We summarize the most relevant related works below. Language generation in the limit. A growing line of work studies a range of questions in the language generation in the limit model and its variants (e.g., [ABCK25; CP25; CPT25; HKMV25; KMV25; KMSV25; KW25; LRT25; MVYZ25; PRR25; RR25; AAK26; CP26; KW26]). Perhaps the most closely related work to ours is that of Charikar and Pabbaraju [CP25] and Mehrotra, Velegkas, Yu, and Zhou [MVYZ25], whose algorithms we build upon. Moreover, the notion of uniform generation we explore in our work was proposed by Li, Raman, and Tewari [LRT25]. We provide a more detailed overview of other works in this area in Appendix B.

Differential privacy under continual release. The continual release model of differential privacy requires algorithms to abide by a strong privacy notion: an observer obtaining all outputs of the algorithm must, in essence, learn almost nothing about the existence of any single input. Since its introduction, this research area has received vast attention, including many recent works (see e.g. [PAK19; FHU23; JKRS+23]). This includes classical estimation problems [CSS11; CR22; HSS23; HUU24], heavy hitters-related problems [CLSX12; EMMM+23], and lower bounds [JRSS23; CLNS+24; ELMZ25].

Technical Overview

In this section, we overview the main ideas and challenges in proving our results. To explain the challenges that the privacy requirement introduces in this setting, we start with identification, and then illustrate that we can design generators that do not suffer from these hurdles.

2.1

Online Model of Private Identification (Theorem 1.5 and Theorem C.5)

Identification lower bound. We begin with our lower bound, which is more involved than the algorithm. Suppose L contains Li , L j with Li ∩ L j = ∞ and Li \ L j < ∞, and assume for contra diction that some algorithm identifies Li , L j . Starting from an enumeration E of Li , the algorithm outputs L j only finitely often with probability one. Using the group-privacy guarantees and the correctness properties of the algorithm, we show how to find a sequence of timesteps tkℓ ℓ∈N such that if we swap elements of E appropriately on these timesteps, we can (i) convert E to an enumeration E′ of L j , and (ii) guarantee that the algorithm cannot identify L j in this enumeration. The technical details to make this work are involved since we need to make infinitely many swaps from E to turn it to an enumeration of L j , while ensuring the algorithm makes infinitely many mistakes. The proof appears in Section 4.2. Identification algorithm. Next, we describe an algorithm that identifies in the limit any countable collection in which every pair of distinct languages has finite intersection; intuitively, the languages are almost disjoint and share only finitely many elements. For intuition, consider two languages { L1 , L2 } with this property. For each Li , maintain an error counter that is equal to the number of stream elements it misses. Then, for any adversarial stream,2 exactly one counter stays at zero while the other grows linearly in the limit. Now, standard continual-release techniques [DNPR10] let us distinguish the two languages. We extend this idea to countable collections by restricting the active search space to finitely many candidate languages at each timestep, which lets us bound the error probability via union bounds.

2.2

Stochastic Model of Private Identification (Theorem 1.6)

We now turn to the stochastic setting of private identification. To design a private algorithm here, a natural approach is to “privatize” an off-the-shelf identification algorithm, like the one from Angluin [Ang80]. Unfortunately, it is not clear how to do that since these algorithms heavily rely on keeping track of a version space, i.e., the set of all consistent 2 This holds even if we allow each element to be repeated a constant amount of times.

languages with the current stream of examples, which can change dramatically on swapping just one element in the stream. To circumvent these, we use the exponential mechanism [MT07]; the main technical hurdles are to (i) design appropriate score functions with low sensitivity, and (ii) since the output space is infinite, the tail of the distribution induced by the exponential mechanism needs to decay sufficiently fast. Intuitively, our scoring function has two components; the first penalizes languages that are not supersets of K and the second penalizes languages that are (strict) supersets of K. The former can be easily achieved by counting how many stream elements each language misses. To achieve the latter, we show it suffices to penalize a language when its tell-tale (Definition 6) has not yet appeared in the stream. We design such a function with small sensitivity which, crucially, has the property that in the stochastic setting we can lower bound the rate at which it is decreasing for all Li ̸= K. This separation is what allows privacy in the stochastic model without additional requirements, while the online setting has a high cost of privacy. To ensure that the tail of the (exponential) distribution decays sufficiently fast and we do not exceed our privacy budget, we run the algorithm in epochs of exponentially increasing size and perform “lazy updates,” i.e., the output remains the same for all timesteps in a given epoch. We sample each language Li with probability proportional to πt (i ) · exp(λut (i )), where ut is the scoring function, πt is a data-independent base measure that heavily downweights languages with large indices, and changes across epochs, and λ is related to the sensitivity of ut and the privacy budget. By carefully choosing all the underlying parameters we can show that the sum of the error probabilities across epochs is finite, thus implying only finitely many identification mistakes almost surely through the Borel–Cantelli lemma (Lemma A.3).

2.3

Private Generation (Theorem 1.1)

Having illustrated the inherent limitations of private identification, we now explain why generation avoids these obstacles. Recall that if Li ⊊ L j , private (online) identification is impossible even for the two-language class { Li , L j }. In contrast, private generation is trivial in this case: since Li ∩ L j is infinite, a generator can safely output elements from this intersection for infinitely many timesteps. This idea also underlies the generators of Kleinberg and Mullainathan [KM24] (and Charikar and Pabbaraju [CP25]). Thus, a natural route is to try to use the exponential mechanism [MT07] to privatize these algorithms. Unfortunately, similar to the identification case, these algorithms are very brittle since they require tracking the version space. Our approach. We instead build on the recent algorithm of Mehrotra, Velegkas, Yu, and Zhou [MVYZ25] (inspired by Charikar and Pabbaraju [CP25]), which is more amenable to privatization because it does not explicitly maintain a version space. Instead, the algorithm assigns each language a priority based on the number of inconsistent strings seen so far, and then (following this priority order) forms incremental intersections until the intersection remains infinite. A careful analysis of the high-priority languages shows that the target language K must eventually be a part of the maintained intersection. Crucially, the algorithm accesses the stream only through these priorities. We can privatize the priority computation at a single timestep via the Laplace mechanism, and then repeat this at sparse timesteps while allocating the privacy budget across repetitions 6

to obtain continual-release guarantees. This is reminiscent of the lazy-updates paradigm from continual-release graph algorithms [FHO21; DLLZ25; ELMZ25; Zho26]. It remains to show that the resulting noisy priorities are accurate enough that K is included in the intersection with probability 1. Once we have computed this infinite subset U ⊆ K, generating an unseen element can be accomplished by truncating this set at a sufficiently long prefix and sampling an element uniformly.

2.4

Sample Complexity of Private Generation (Theorems 1.2 and 1.3)

We now study the sample complexity of private generation under uniform bounds, meaning bounds that do not depend on the target language K and its enumeration. The analysis in this setting turns out to be significantly more delicate than the previous one. Without privacy, such uniform bounds exist if and only if L has finite closure dimension (Definition 2). Sample complexity upper bound (Theorem 1.2). We begin with finite collections, which admit uniform bounds in the non-private setting [KM24]. Since the algorithm from the previous subsection does not exploit finiteness, we analyze a different procedure here.3 A simple (non-private) algorithm for uniformly generating finite collections is as follows: output the smallest unseen element from the closure (i.e., intersection) of all consistent languages, where a language L is consistent if L ⊇ Sn . To prove Theorem 1.2, we show that this algorithm can be privatized via the exponential mechanism with a carefully designed score. To be more precise, our score function will assign scores to subsets of languages, and our algorithm will sample a subset S of languages and output their closure Cl(LS := { Li : i ∈ S}).4 We will design a score function which comes with the guarantee that, as n → ∞, with probability 1, the sampled subcollection LS (P1) contains K and (P2) Cl(LS ) is infinite. Achieving Property (P2) is straightforward: it suffices to ensure that Cl(LS ) contains at least d + 1 elements, where d is the closure dimension of L . Then the definition of closure dimension implies |Cl(LS )| = ∞ [LRT25]. The main work is establishing (P1). A simple score rewards LS proportional to how many enumerated elements lie in Cl(LS ), but this does not differentiate between K and its supersets. So any superset of K has the same score and, hence, the same probability of being sampled as K. So the probability of sampling K can be as small as 1/c, where c is the number of supersets of K in L . One could repeat the exponential mechanism tn times to amplify probability of sampling K, but this would require tn → ∞ with n and would incur additional privacy loss with each re-sampling. Instead, we design a different score function which balances two competing goals: (G1) favoring larger subcollections and (G2) favoring subcollections whose closure contains more elements from the input enumeration. The key observation is simple: if K ∈ / LS , then adding K yields a subcollection that weakly improves both (G1) (it is larger) and (G2) (including K does not remove any elements from closure). We show that observation is enough to conclude that, with sufficiently high probability in n, the exponential mechanism will sample a subcollection that contains K. 3 Note that while our algorithm here will be able to achieve a uniform sample complexity, it is incomparable to the

algorithm in the previous subsection result since the current algorithm does not generate from all countable collections. 4 Given this closure, one can always privately post-process to sample one unseen element from it; Lemma 4.1.

Sample complexity lower bound (Theorem 1.3). Having proved an upper bound for finite collections, it is natural to ask whether it is tight and whether a similar guarantee extends to all countable collections with finite closure dimension. We show the upper bound is tight, and moreover that there exist collections with closure dimension zero that still do not admit any uniform private bound. Our lower bound uses the standard packing lower bound approach for DP [HT10]. This framework proceeds roughly as follows. Let M : Xn → [ N ] be an ε-DP mechanism with discrete output space [ N ] and suppose that every v ∈ [ N ] is the unique correct answer to M( X ′ ) for some X ′ ∈ Xn . For any dataset X ∈ Xn , there must be at least one output v ∈ [ N ] such that Pr[ M ( X ) = v] ≤ 1/N . By assumption, there is some X ′ ∈ Xn where Pr[ M( X ′ ) = v] ≥ 2/3 since v is the uniquely correct response for dataset X ′ . By the definition of DP, 2/3 ≤ Pr[ M( X ′ ) = v] ≤ enε · Pr[ M ( X ) = v] ≤ enε/N . In other words, n ≥ Ω((log N )/ε). In our lower bound construction, by an appropriate postprocessing we may take the relevant output space to be a subset of the 2k index sets I ⊆ [k ], each encoding an infinite intersection T i ∈ I Li of languages from a size-k collection. The main technical challenge is to construct a size k collection that “packs” as many different unique correct responses as possible for input streams of e (2k ) distinct responses and thus length n. We do so via a Sperner family, which provides N = Ω gives the desired lower bound.

Model and Preliminaries

In this section, we introduce differential privacy and the model of language generation in the limit. Notation. Let X be a countable universe of strings. For instance, if Σ is a finite alphabet (e.g., { a, b, . . . , z}), then X = Σ∗ can be the set of all finite-length strings formed by concatenating symbols from Σ. We define a language L as an infinite subset of X. A countable collection of languages is denoted by L = { L1 , L2 , . . . }. We define a generating algorithm G = (Gn )n∈N as a sequence of (possibly randomized) mappings Gn : Xn → 2X parametrized by the input size n. In words, the generator maps a finite training set to a (potentially infinite)5 set of elements.

3.1

Language Generation and Identification in the Limit

We now formally define language generation in the limit, both in an online and a statistical model. Online model. We begin with an extension of the online model that was introduced by [KM24], which handles randomized generators as necessary for DP. Definition 1 (Language Generation in the Limit [KM24]). Let L = { L1 , L2 , . . . } be a collection of languages, G = (Gn ) be a generating algorithm, and K ∈ L be some target language. A randomized algorithm G is said to generate from K in the limit if, for all enumerations of K, with probability 1, there is some n⋆ ∈ N such that for all steps n ≥ n⋆ , the algorithm’s output satisfies Gn (Sn ) ⊆ (K \ Sn ), where Sn is the set of the first n elements given in the input. The collection L allows for generation in the limit if there is an algorithm G that generates from K in the limit for any K ∈ L . 5 This is to align with the set-based and element-based notions of generations that have been considered in the literature.

We remark that Kleinberg and Mullainathan [KM24] originally studied deterministic generation algorithms; follow-up works studied this natural randomized version, whose analogue has also been studied for identification [Ang88; CPT25; KMV25]. To gain some intuition about Definition 1, consider the universe X = Σ∗ and the countable collection of length-threshold languages L = { L1 , L2 , . . .} where Lℓ = { x ∈ Σ∗ : | x | ≥ ℓ}. Suppose the target language is K = Lℓ∗ for some unknown ℓ∗ ∈ N, and the adversary enumerates K as x1 , x2 , . . .. After observing Sn = { x1 , . . . , xn }, we must have ℓ∗ ≤ minx∈Sn | x |. Hence every string of length strictly greater than minx∈Sn | x | lies in every candidate language consistent with Sn , and in particular lies in K. A valid generator is therefore: for n ≥ 1, let mn = minx∈Sn | x | and output the lexicographically smallest string y ∈ Σmn +1 with y ∈ / Sn . We will also frequently make use of the closure of a language collection, as well as the closure dimension, which characterizes uniform generation, defined below. Definition 2 (Closure of Language Collection and Closure Dimension [LRT25]). Let L be a language collection. The closure of L , denoted as Cl(L ), is the intersection of all the languages in L , i.e., T Cl(L ) := L∈L L. The closure dimension of collection L is the smallest d ∈ {−1} ∪ N such that for any subcollection L ′ ⊆ L of languages, either |Cl(L ′ )| = ∞, or |Cl(L ′ )| ≤ d. Throughout this paper, we allow our algorithms access to the languages in the form of a membership oracle: for every i ∈ N and x ∈ X, we can decide whether x ∈ Li . Sometimes, we will also allow our algorithms to use the other existing oracles introduced by prior work. Language identification. We now define the preceding notion of language identification. Definition 3 (Language Identification in the Limit [Gol67]). Fix a collection L = { L1 , L2 , . . . }. An adversary chooses an unknown target language K ∈ L and enumerates its strings as x1 , x2 , . . . (ensuring that every x ∈ K appears at some time). At each step n, the identification algorithm I observes x1 , . . . , xn and outputs an index in as its current guess for the target. We say that I identifies K in the limit if there is a time n⋆ after which it never changes its mind and its stabilized guess is correct: for all n ≥ n⋆ we have in = in⋆ and Lin = K. The collection L is identifiable in the limit if there exists an identification algorithm that succeeds for every K ∈ L and every enumeration. Identification is a strictly stronger requirement than generation and is achievable only for restricted collections. Angluin [Ang80] provided a characterization of which collections are identifiable in the limit (see Definition 6), showing that identifiability imposes stringent structural constraints on the collection. Stochastic model of identification. Next, we describe the stochastic model of language identification, introduced by Angluin [Ang88] and studied by several follow-up works. Here, the adversary chooses some target K ∈ L and some distribution D with supp( D ) = K. Then, in every timestep t ∈ N a new string is drawn i.i.d. from K and is revealed to the learner, whose task is to figure out the index of the target. Thus, a distribution D is called valid if supp( D ) ∈ L , i.e., it is entirely supported on a language in L . Naturally, the success criterion for an identification algorithm in this setting is that for every K ∈ L and every D with supp( D ) = K, then the algorithm will make

only finitely many mistakes identifying K on an (infinite) i.i.d. stream from D, where the probability is both with respect to its internal randomness and the randomness of the stream. The formal definition (Definition 7) is deferred to Appendix A. Interestingly, Angluin [Ang88] showed that L is identifiable in the stochastic setting if and only if it is identifiable in Gold’s setting.

3.2

Differential Privacy and Continual Release

Differential privacy [DMNS06] is a stability notion for randomized algorithms. Intuitively, it protects users’ data by ensuring that the output of the algorithm does not depend too strongly on any single individual’s data. Definition 4 (Pure Differential Privacy). Two datasets (or sets of strings) X, X ′ ∈ Xn (for n ∈ N) are neighboring if they differ in exactly one coordinate. Fix an ε > 0. A (randomized) algorithm Gn : Xn → ∆ (X) is ε-DP if for all neighboring datasets X and X ′ and all measurable events E ⊆ ∆ (X), Pr Gn ( X ) ∈ E ≤ eε · Pr Gn ( X ′ ) ∈ E . As language generation is a continual learning problem, with strings being continually generated, we must ensure that the entire process is private as opposed to a single output. This is precisely captured by the continual release [DNPR10; CSS11] model of differential privacy. ′ ∈ Xn (for n ∈ N ∪ { ∞ }) Definition 5 (Continual Release). Two streams (sequences) of strings x1:n , x1:n are neighboring if they differ at exactly one timestep. Fix an ε > 0. A (randomized) algorithm Gn : Xn → ∆ (X)n that outputs a distribution ∆ (X)i after observing x1:i (i ∈ [n]) is ε-DP if for all neighboring streams ′ and all measurable events E ⊆ ∆ (X)n , Pr G ( x ) ∈ E ≤ eε · Pr G ( x ′ ) ∈ E . x1:n and x1:n n 1:n n 1:n

We emphasize that Definition 5 requires the entire output stream to satisfy DP, while Definition 4 only requires the output at a single timestep to satisfy DP.

Proofs of Theorems 1.1 and 1.5

In this section, we prove Theorems 1.1 and 1.5; the remaining proofs appear in Appendix C.

4.1

Proof of Theorem 1.1 (Private Generation for Countable Collections)

Next, we prove Theorem 1.1, which asserts that Algorithm 1 is ε-DP in the continual release model and generates from any countable collection with probability 1. Before proving Theorem 1.1, we present a useful lemma that reduces the task of privately generating valid unseen strings from the target language K to computing an infinite subset of K. Lemma 4.1. Let G be an ε-DP algorithm in the continual release model that, for any countable collection L , has the property that, with probability 1, there is some n⋆ ∈ N after which G computes an infinite subset Un ⊆ K of the target language K for all n ≥ n⋆ . Then for any sequence of failure probabilities β n ∈ (0, 1), there is a data-oblivious postprocessing M ◦ G that is ε-DP in the continual release model and outputs an unseen element wn ∈ Un \ ( x1:n ∪ w1:n−1 ) from Un ⊆ K at each n ≥ n⋆ with probability 1 − βn . 10

Proof of Lemma 4.1. At each time step n ∈ N, M simply extracts a finite subset Vn ⊆ Un of size |Vn | = 2n β n and samples a uniform random string from Vn . Since | x1:n ∪ w1:n−1 | ≤ 2n, this avoids one of the observed strings with probability 1 − β n , as desired. We are now ready to prove Theorem 1.1. Proof of Theorem 1.1. We analyze privacy and utility separately. Privacy analysis. The algorithm accesses the private stream only when releasing noisy consistency counts e ri,t . This occurs at sparse steps tk = k6 for k ∈ N, where it computes the vector of true counts q(k) := (r1,tk , . . . , rk,tk ) and adds independent Laplace noise Lap(bk ) to each coordinate, 1/3 where bk := tk /ε 0 = k3/ε 0 . ′ differing in exactly one element xτ . For any speConsider two neighboring streams x1:∞ , x1:∞ cific step tk , the L1 -sensitivity of the vector query q(k) is bounded by ∆1 (q(k) ) = ∑ik=1 ri,tk ( D ) − ri,tk ( D ′ ) ≤ k, as removing or changing one element can change the set difference x1:tk \ Li by at most 1 element for each language Li . By simple composition of differential privacy (Proposition A.4), the total privacy loss is ∞

∞ ∞ ∆1 ( q ( k ) ) k 1 π2 =∑ 3 = ε0 ∑ 2 = ε0 · = ε. bk k /ε 0 k 6 k =1 k =1 k =1

ε total = ∑

Thus, the algorithm satisfies pure differential privacy. Utility analysis. We must show that generation in the limit is achieved almost surely. This requires that for large enough t, the algorithm selects an infinite set of strings (intersection of languages) contained in the target language K = Li⋆ . Li⋆ is consistent with the input stream. Intuitively, we show that (1) Li⋆ maintains a bounded priority score, and (2) any language L j with “high error” will eventually have a priority score larger than Li⋆ . Define the “bad” event at step tk = k6 for language i ≤ k as the noise overwhelming the signal: Ei,k =

e ri,tk − ri,tk

t ≥ k2 200i

Using the tail bound for Lap(bk ), observing tk /bk = k6 /(k3 /ε 0 ) = ε 0 k3 , we have: Pr[ Ei,k ] = t /(200i2 )

− k

− εk

bk e = e 200i2 . Since i ≤ k, we have k3 /i2 ≥ k. Thus Pr[ Ei,k ] ≤ exp(−Ω(ε 0 k)). Summing over at most k2 events indexed by k ≥ 1 and 1 ≤ i ≤ k, we see the total failure probability is summable

−ε 0 k

since ∑k≥1,i≤k Pr [ Ei,k ] ≤ ∑k≥1 e 200 k2 < ∞. Now, by the Borel–Cantelli lemma, with probability 1, at most a finite number of bad events occur. Let k be the largest index such that some Ei,k occurs. Such a k exists almost surely from our work above. We know that Ei,k for k > k, i ≤ k does not occur. Conditioned on the complement of these bad events, the following hold. 6

1. Target Language Li⋆ : The true error is ri⋆ ,t = 0. For t ≥ k , the observed noisy error is e ri⋆ ,t < ei⋆ is eri⋆ ,t/t > 1/200(i⋆ )2 . Since 1/300 < t/200(i⋆ )2 . The condition for incrementing the counter N 11

ei⋆ stops growing, and its priority Pei⋆ is bounded by a 1/200, this condition is never met. Thus, N constant P⋆ ≥ i⋆ . 6

2. High Error Languages: For t ≥ k , we ensure that the following holds e r ri,t 1 1 =⇒ i,t > > 2 t 100i t 200i2

and

e ri,t r 1 1 =⇒ i,t ≤ . ≤ 2 t 300i t 200i2

Thus, any language violating the error threshold by a small margin will always have its counter incremented, and the counter for any language below the threshold by a small margin eventually stops changing.

Algorithm 1: Private Approximate Intersection Data: Stream of data elements x1 , x2 , . . . and a language collection { Li }i≥1 Result: Privacy parameter ε > 0 ei ← 0 for all i; 1 Initialize consistency counts N 2 2 Set ε 0 ← 6ε/π ; 3 for t ← 1 to ∞ do 4 Receive new string xt and initialize counter k ← ⌊t1/6 ⌋; 5 if t = k6 then 6 for i ← 1 to k do 7 Compute true consistency-count ri,t ← | x1:t \ Li |; 8 Compute noisy consistency-count e ri,t ← max 0, ri,t + Lap(t1/3 /ε 0 ) 9 If noisy count is large, e ri,t /t > 1/(200i2 ), ei ← N ei + 1; then update consistency count N ei ; 10 Update priority Pei ← i + N 11 Re-order { L1 , . . . , Lk } in increasing priority, tie-breaking by index, as { Lit (1) , . . . , Lit (k) }, i.e., for each j ∈ [k − 1], ensure either Peit ( j) < Peit ( j+1) or Peit ( j) = Pit ( j+1) and i t ( j ) < i t ( j + 1); 12 Compute maximal incremental infinite intersection j

Jt ← max{ j ∈ [k ] : |∩ j=1 Lit ( j) | = ∞}; T Compute j≤ Jt Lit ( j) = {z1 , z2 , . . . } and output a uniformly random element wn ∈ {z1 , . . . , z200t3 };

We argue that for all large enough t, languages with priority at most P⋆ (which include Li⋆ ) must have summable error. Indeed, the set LP⋆ := { Li : i ≤ P⋆ } is a finite set containing Li⋆ . Moreover, any L j ∈ / LP⋆ will have priority Pej ≥ P⋆ so that it will always come after Li⋆ . By the finiteness of LP⋆ , for sufficiently large t, every Li ∈ LP⋆ whose error exceeds 1/100i2 infinitely often will have priority exceeding P⋆ . Thus eventually, every language Li ordered before Li⋆ must have summable error at most 1/100i2 . Let Cl(L (k )) denote the intersection of all languages in L (k ) ⊆ LP⋆ , the collection of languages ordered before Li⋆ at step tk , including Li⋆ itself. If we show that |Cl(L (k ))| = ∞, we are

done as the incremental intersection is guaranteed to include Li⋆ . Indeed, as k → ∞,

|Cl(L (k))| ≥ | x1:tk ∩ Cl(L (k))| ≥ tk

ri,t 1 − ∑ L ∈L ( k ) k i tk

≥ tk

1 1 − ∑ i ≥1 100i2

≥

tk . 2

In particular, |Cl(L (k ))| = ∞. Finally, we apply Lemma 4.1 to see that sampling a uniform random string among a size 200t3 subset of an infinite subset of the target language repeats a seen element with summable proba1 bility 100t 2 and preserves privacy. By another application of the Borel–Cantelli lemma, we see that with probability 1, Algorithm 1 outputs unseen elements after some finite time.

4.1.1

Non-Uniform Generation Guarantee

Next, we explain how the algorithm G (Algorithm 1) achieves non-uniform generation. In particular, for any ε > 0 and β > 0, any countable collection L , and any target language K ∈ L , there exists t = t(ε, β, L , K ) such that G is ε-DP in the continual release model, and for any enumeration of K, generates from K after step t with probability 1 − β. Remark 4.2 (Non-Uniform Generation). Fix any ε, β > 0, a collection L , and a target language K = Li⋆ . Using the tail bound of Laplace distribution as in utility analysis of the proof above, there exists t1 = t1 (ε, β, L , K ) such that with probability at least 1 − β/2, we have eri⋆ ,t/t ≤ 100i1 ⋆ 2 for all ei⋆ ≤ i⋆ + t1 and it stays fixed for all t ≥ t1 . Using the tail t ≥ t1 , in which case we have Pei⋆ = i⋆ + N bound of Laplace distribution again, there exists t2 = t2 (ε, β, L , K, t1 ) such that with probability 1 ⋆ at least 1 − β/2, we have |eri,t/t − ri,t/t| ≤ 200i 2 for all i ≤ i + t1 and t ≥ t2 . Now, conditional on these events which take place with probability at least 1 − β, there exists t3 = t3 (L , K, t1 , t2 ) such that the target language K participates in the maximal incremental infinite intersection at step t for all t ≥ t3 . To see this, note that for t3 large enough, the priority of the target language K stays fixed and satisfies Pei⋆ ≤ i⋆ + t1 , and all the languages Li with indices at 1 ⋆ most i⋆ + t1 satisfy |eri,t/t − ri,t/t| ≤ 200i 2 . Let B : = max{|Cl(LS )| : S ⊆ [ i + t1 ], |Cl(LS )| < ∞ } denote the size of the maximum finite intersection of a subcollection of the languages with indices at most i⋆ + t1 . For t > 2B, either all the languages with priorities at most the priority of K have an infinite intersection, in which case we are done and G starts generating from K after step t, or r 1 the languages with priorities at most the priority of K have a finite intersection and i,tt > 100i 2 for some “bad” language Li that comes before K in the priority ordering at step t. However, in the latter case, the priority of “bad” language increments by 1, and this can only happen for a finite number of steps depending on i⋆ and t1 , after which we end up in the first case.

4.2

Proof of Theorem 1.5 (Private Online Identification Lower Bound)

Proof of Theorem 1.5. Fix ε > 0 and suppose for contradiction that there exists an ε-DP continual release identification algorithm A for L . Let Li , L j ∈ L be distinct such that | Li ∩ L j | = ∞ and

(1)

This will be useful because enumerations can replace the m elements of F by m distinct elements of V while staying duplicate-free. Group privacy for continual release. By group privacy (Proposition A.6), if A is ε-DP and two ′ differ in at most k time steps, then for every event E over the first T outputs, streams x1:T , x1:T Pr[ A( x )1:T ∈ E ] ≤ ekε Pr A( x ′ )1:T ∈ E .

(2)

Order X canonically. Further, enumerate F = { f 1 , . . . , f m } and I = { a1 , a2 , . . . } in canonical order and define a duplicate-free enumeration of Li : E := ( f 1 , . . . , f m , a1 , a2 , a3 , . . . ). Since A identifies Li on every (duplicate-free) enumeration, given E, with probability 1, A outputs the correct i all but finitely many times. In particular, for NjS ( T ) := {t ≤ T : A outputs index j at time t on input stream S} , we have (3) Pr NjE ( T ) ≥ T/2 −−−→ 0. T →∞

Consider a canonical enumeration of V = L j \ Li , i.e., V = {u1 , u2 , . . . }. By (1), u1 , . . . , um exist and are distinct. Define E(0) by replacing the first m elements of E with u1 , . . . , um : E(0) := (u1 , . . . , um , a1 , a2 , a3 , . . . ). Then E(0) is duplicate-free and every element of E(0) lies in L j . Moreover, E and E(0) differ in exactly m positions, so applying (2) to the event { Nj (∞) = ∞}, we get that A outputs j only finitely many times almost surely on input E(0) as well. Hence, (0) Pr NjE ( T ) ≥ T/2 −−−→ 0. T →∞

(4)

−2kε

Now define δk := e k2 . Hence, it holds that ∞

∞

e−kε < ∞. k2 k =1

∑ δk ekε = ∑

k =1

By (4), we can choose an increasing sequence of times T1 < T2 < · · · such that for all k ≥ 1, (0) Pr NjE ( Tk ) ≥ Tk /2 ≤ δk .

(5)

We now perform an infinite sequence of single-coordinate edits at the times Tk that turns E(0) into an enumeration of L j , while ensuring that up to time Tk we changed at most k positions (so we can (0)

apply group privacy with parameter k). Let U (0) := L j \ { Et : t ≥ 1}. Concretely, U (0) contains exactly the “still-missing” elements of V, namely U (0) = {um+1 , um+2 , . . . } (possibly empty if 14

|V | = m). We define inductively streams E(k) and pools U (k) as follows. Assume E(k−1) has been defined, is duplicate-free and contains only elements in L j . If U (0) = ∅, then E(0) already enumerates L j (it contains all of V and all of I), and we may set E′′ := E(0) and skip the subsequent steps. Otherwise, for each k ≥ 1: • Let vk be the smallest element of U (k−1) in the canonical order. ( k −1)

• Let yk := ETk

be the element currently occupying position Tk . (k)

• Define E(k) by a single replacement at time Tk : Et

( k −1)

is vk if t = Tk and, otherwise, it is Et • Update the pool by reverting the insertion and deletion: U (k) := U (k−1) \ {vk } ∪ {yk }.

Next, we prove that this maintains duplicate freeness and correctness of the pool. We claim by induction on k: (k)

1. E(k) is duplicate-free and Et

∈ L j for all t.

(k)

2. U (k) = L j \ { Et : t ≥ 1} (i.e., U (k) is exactly the set of elements of L j still missing from the current stream). This is immediate: by the inductive hypothesis, U (k−1) is disjoint from the range of E(k−1) , so vk ∈ / ( k −1) } and inserting vk introduces no duplicate; simultaneously we remove yk from the stream { Et and add it back to the pool, preserving both disjointness and the identity U (k) = L j \ range( E(k) ). Now define the limiting stream E′′ as vk if t = Tk for some k and, otherwise, define it as (0) Et . Since the Tk ’s are strictly increasing, each coordinate is modified at most once, so E′′ is welldefined. E′′ enumerates L j . From the invariant U (k) = L j \ range( E(k) ) and the fact that once a value is placed at coordinate Tk it is never changed again, we get the following dichotomy for any x ∈ L j : either x is never placed out and it stays in the final stream, or it is placed out once (when it equals some yk ) and then it enters the pool. Because at each phase we insert the smallest element of the pool, and because the canonical order is induced by an enumeration of X (so each element has finitely many predecessors), every fixed x ∈ L j can be bypassed only finitely many times before it becomes the smallest pool element and is inserted at some later phase. Once inserted, it is never placed out again. Therefore every x ∈ L j appears in E′′ at some finite index, and E′′ is a duplicate-free enumeration of L j . ′′ ′′ For each k, consider the event Fk := NjE ( Tk ) ≥ Tk /2 . By construction, the prefixes E1:T k (0)

and E1:Tk differ in exactly the k positions T1 , . . . , Tk , hence in at most k positions. Applying group privacy (2) at horizon Tk and then (5) yields (0) Pr Fk under input E′′ ≤ ekε · Pr NjE ( Tk ) ≥ Tk /2 ≤ ekε δk . Since ∑k≥1 ekε δk < ∞, the first Borel–Cantelli lemma implies that with probability 1 only finitely many events Fk occur when A is run on input E′′ . However, if A identified L j on the valid enumeration E′′ , then with probability 1 there would ′′ exist a time τ such that A outputs j at every round t ≥ τ. Then for all k with Tk ≥ 2τ, NjE ( Tk ) ≥ 15

Tk − τ ≥ Tk /2, so Fk would occur for all sufficiently large k, and hence infinitely often, which is a contradiction. Therefore, A cannot identify L j on the enumeration E′′ , contradicting the assumption that A identifies L in the limit. This completes the proof.

Conclusion

In this work we initiate the study of privacy in language generation and identification in the limit. Surprisingly, online generation remains achievable under strong privacy constraints, whereas online identification is severely restricted. Unlike the online setting, in the stochastic model of Angluin [Ang88], private identification becomes achievable for all collections which are identifiable without privacy. This reveals a strong separation between private online and stochastic identification, which is absent in non-private settings. Our work suggests several future directions: including investigating more lenient variants of differential privacy [BS16; Mir17], exploring the interplay between privacy and breadth [CP25; KMV25; KW25; PRR25; KMV26; KW26], and studying if private algorithms can be designed for uncountable collections.

Acknowledgments We thank anonymous reviewers for comments that helped improve the presentation of this work. Felix Zhou acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC). Xifan Yu is supported in part by ONR Award N00014-24-1-2611.

References [AAK26]

[ABCK25]

[ALMM19]

[Ang80]

[Ang88]

[BBDS+24]

[BHMv+21]

[BLM20]

[BPZ26]

[BS16]

[CLNS+24]

Antonios Anastasopoulos, Giuseppe Ateniese, and Evgenios M. Kornaropoulos. Safe Language Generation in the Limit. 2026. arXiv: 2601.08648 [cs.CL]. URL: https://arxiv. org/abs/2601.08648 (cit. on p. 4). Marcelo Arenas, Pablo Barceló, Luis Cofré, and Alexander Kozachinskiy. Language Generation: Complexity Barriers and Implications for Learning. 2025. arXiv: 2511.05759 [cs.CL]. URL : https://arxiv.org/abs/2511.05759 (cit. on p. 4). Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. “Private PAC learning implies finite Littlestone dimension”. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC 2019. Association for Computing Machinery, 2019, pp. 852–860. URL : https://doi.org/10.1145/3313276.3316312 (cit. on p. 1). Dana Angluin. “Inductive Inference of Formal Languages From Positive Data”. In: Information and Control 45.2 (1980), pp. 117–135. URL: https://www.sciencedirect.com/ science/article/pii/S0019995880902855 (cit. on pp. 4, 5, 9, 22, 36). Dana Angluin. Identifying Languages From Stochastic Examples. Yale University. Department of Computer Science, 1988. URL: http://www.cs.yale.edu/publications/techreports/ tr614.pdf (cit. on pp. 4, 9, 10, 16, 36). Adam Block, Mark Bun, Rathin Desai, Abhishek Shetty, and Zhiwei Steven Wu. “OracleEfficient Differentially Private Learning with Public Data”. In: Advances in Neural Information Processing Systems. Vol. 37. Curran Associates, Inc., 2024, pp. 113191–113233. URL: https: //proceedings.neurips.cc/paper_files/paper/2024/file/cd9664c7094d90e512ce27f2fd Paper-Conference.pdf (cit. on p. 1). Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff. “A Theory of Universal Learning”. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2021. Association for Computing Machinery, 2021, pp. 532–541. URL: https://doi.org/10.1145/3406325.3451087 (cit. on p. 4). Mark Bun, Roi Livni, and Shay Moran. “An Equivalence Between Private Classification and Online Prediction”. In: 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). 2020, pp. 389–402 (cit. on p. 1). Yannan Bai, Debmalya Panigrahi, and Ian Zhang. “Language Generation in the Limit: Noise, Loss, and Feedback”. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2026, pp. 794–816. eprint: https://epubs.siam.org/doi/pdf/ 10.1137/1.9781611978971.31. URL: https://epubs.siam.org/doi/abs/10. 1137/1.9781611978971.31 (cit. on p. 24). Mark Bun and Thomas Steinke. “Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds”. In: Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I. Vol. 9985. Lecture Notes in Computer Science. 2016, pp. 635–658. URL: https://doi.org/10.1007/9783-662-53641-4%5C_24 (cit. on p. 16). Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. “Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries”. In: The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada. Vol. 247. Proceedings of Machine Learning Research. PMLR, 2024, pp. 1200–1222. URL: https: //proceedings.mlr.press/v247/cohen24b.html (cit. on pp. 2, 5).

[CLSX12]

[CP25]

[CP26]

[CPT25]

[CR22]

[CSS11]

[CTWJ+21]

[DLLZ25] [DMNS06]

[DNPR10]

[DR14]

[ELMZ25]

[EMMM+23]

T.-H. Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. “Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams”. In: Privacy Enhancing Technologies Symposium (PETS). 2012, pp. 140–159 (cit. on p. 5). Moses Charikar and Chirag Pabbaraju. “Exploring Facets of Language Generation in the Limit”. In: Thirty-eighth Conference on Learning Theory (COLT 2025). Proceedings of Machine Learning Research. PMLR, 2025. URL: https://arxiv.org/abs/2411.09642 (cit. on pp. 1, 4, 6, 16, 24). Moses Charikar and Chirag Pabbaraju. “Pareto-optimal Non-uniform Language Generation”. In: Proceedings of the 37th International Conference on Algorithmic Learning Theory. ALT 2026. 2026. arXiv: 2510.02795. URL: https://arxiv.org/abs/2510.02795 (cit. on p. 4). Moses Charikar, Chirag Pabbaraju, and Ambuj Tewari. “A Characterization of List Language Identification in the Limit”. In: arXiv preprint arXiv:2511.04103 (2025). URL: https: //arxiv.org/abs/2511.04103 (cit. on pp. 4, 9). Adrian Rivera Cardoso and Ryan Rogers. “Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown”. In: International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event. Vol. 151. Proceedings of Machine Learning Research. PMLR, 2022, pp. 2397–2419. URL: https:// proceedings.mlr.press/v151/rivera-cardoso22a.html (cit. on p. 5). T.-H. Hubert Chan, Elaine Shi, and Dawn Song. “Private and Continual Release of Statistics”. In: ACM Trans. Inf. Syst. Secur. 14.3 (2011), 26:1–26:24. URL: https://doi.org/10. 1145/2043621.2043626 (cit. on pp. 2, 5, 10). Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. “Extracting training data from large language models”. In: 30th USENIX security symposium (USENIX Security 21). 2021, pp. 2633–2650 (cit. on p. 1). Michael Dinitz, George Z Li, Quanquan C Liu, and Felix Zhou. “Differentially Private Matchings”. In: arXiv preprint arXiv:2501.00926 (2025) (cit. on p. 7). Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. “Calibrating Noise to Sensitivity in Private Data Analysis”. In: Theory of Cryptography. Springer Berlin Heidelberg, 2006, pp. 265–284 (cit. on pp. 1, 10). Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. “Differential privacy under continual observation”. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010. ACM, 2010, pp. 715–724. URL : https://doi.org/10.1145/1806689.1806787 (cit. on pp. 2, 5, 10). Cynthia Dwork and Aaron Roth. “The Algorithmic Foundations of Differential Privacy”. In: Found. Trends Theor. Comput. Sci. 9.3-4 (2014), pp. 211–407. URL: https://doi.org/10. 1561/0400000042 (cit. on p. 23). Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, and Felix Zhou. “Sublinear Space Graph Algorithms in the Continual Release Model”. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2025, Berkeley, CA, USA, August 11-13, 2025. Vol. 353. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, 40:1–40:27. URL: https://doi.org/10.4230/LIPIcs.APPROX/ RANDOM.2025.40 (cit. on pp. 2, 5, 7). Alessandro Epasto, Jieming Mao, Andres Muñoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. “Differentially Private Continual Releases of Streaming Frequency Moment Estimations”. In: 14th Innovations in Theoretical Computer Science Conference, ITCS

[FHMS+24]

[FHO21]

[FHU23]

[GGKM21]

[Gol67]

[HKMV25]

[HMST25]

[HSS23]

[HT10]

[HUU24]

[JKRS+23]

2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA. Vol. 251. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, 48:1–48:24. URL: https://doi.org/10.4230/ LIPIcs.ITCS.2023.48 (cit. on p. 5). Simone Fioravanti, Steve Hanneke, Shay Moran, Hilla Schefler, and Iska Tsubari. “Ramsey Theorems for Trees and a General ‘Private Learning Implies Online Learning’ Theorem”. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). 2024, pp. 1983– 2009 (cit. on p. 1). Hendrik Fichtenberger, Monika Henzinger, and Lara Ost. “Differentially Private Algorithms for Graphs Under Continual Observation”. In: 29th Annual European Symposium on Algorithms, ESA 2021, Lisbon, Portugal (Virtual Conference), September 6-8, 2021. Vol. 204. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 42:1–42:16. URL: https://doi. org/10.4230/LIPIcs.ESA.2021.42 (cit. on p. 7). Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. “Constant matters: Finegrained error bound on differentially private continual observation”. In: International Conference on Machine Learning. PMLR. 2023, pp. 10072–10092 (cit. on p. 5). Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. “Sample-efficient proper PAC learning with approximate differential privacy”. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2021. Association for Computing Machinery, 2021, pp. 183–196. URL: https://doi.org/10.1145/3406325.3451028 (cit. on p. 1). E. Mark Gold. “Language Identification in the Limit”. In: Information and Control 10.5 (1967), pp. 447–474. URL: https : / / www . sciencedirect . com / science / article / pii / S0019995867911655 (cit. on pp. 1, 3, 9). Steve Hanneke, Amin Karbasi, Anay Mehrotra, and Grigoris Velegkas. “On Union-Closedness of Language Generation”. In: The Thirty-ninth Annual Conference on Neural Information Processing Systems. 2025. URL: https://openreview.net/forum?id=6h7HLx1kbH (cit. on p. 4). Steve Hanneke, Shay Moran, Hilla Schefler, and Iska Tsubari. “Private List Learnability vs. Online List Learnability”. In: Proceedings of Thirty Eighth Conference on Learning Theory. Vol. 291. Proceedings of Machine Learning Research. PMLR, 30 Jun–04 Jul 2025, pp. 5173– 5213. URL: https : / / proceedings . mlr . press / v291 / hanneke25d . html (cit. on p. 1). Monika Henzinger, AR Sricharan, and Teresa Anna Steiner. “Differentially Private Histogram, Predecessor, and Set Cardinality under Continual Observation”. In: arXiv preprint arXiv:2306.10428 (2023) (cit. on p. 5). Moritz Hardt and Kunal Talwar. “On the geometry of differential privacy”. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010. ACM, 2010, pp. 705–714. URL: https://doi.org/10.1145/1806689. 1806786 (cit. on p. 8). Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. “A unifying framework for differentially private sums under continual observation”. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2024, pp. 995–1018 (cit. on p. 5). Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. “Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation”. In: Advances in Neural Information Processing Systems 36: Annual Conference

[JRSS23]

[KLNR+11]

[KM24] [KMSV25]

[KMV25]

[KMV26]

[KW25]

[KW26]

[Lit88]

[LRT25]

[LTLH22]

on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023. 2023 (cit. on p. 5). Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. “The Price of Differential Privacy under Continual Observation”. In: International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA. Vol. 202. Proceedings of Machine Learning Research. PMLR, 2023, pp. 14654–14678. URL: https://proceedings. mlr.press/v202/jain23b.html (cit. on pp. 2, 5). Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. “What Can We Learn Privately?” In: SIAM Journal on Computing 40.3 (2011), pp. 793–826. eprint: https://doi.org/10.1137/090756090. URL: https://doi. org/10.1137/090756090 (cit. on p. 1). Jon Kleinberg and Sendhil Mullainathan. “Language generation in the limit”. In: Advances in Neural Information Processing Systems 37 (2024), pp. 66058–66079 (cit. on pp. 1, 2, 6–9, 24). Amin Karbasi, Omar Montasser, John Sous, and Grigoris Velegkas. “(Im)possibility of Automated Hallucination Detection in Large Language Models”. In: Second Conference on Language Modeling. 2025. URL: https://openreview.net/forum?id=e5jWdZIX0Q (cit. on p. 4). Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. “On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC’25). Association for Computing Machinery, 2025. URL: https://arxiv.org/abs/2411.09642 (cit. on pp. 1, 4, 9, 16, 24). Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. “On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability”. In: Proceedings of the 37th International Conference on Algorithmic Learning Theory (ALT 2026). Proceedings of Machine Learning Research. Accepted to ALT 2026. Feb. 2026. arXiv: 2412.18530 [cs.LG]. URL : https://arxiv.org/abs/2412.18530 (cit. on pp. 4, 16, 24). Jon Kleinberg and Fan Wei. “Density Measures for Language Generation”. In: Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025). To appear. IEEE, 2025. arXiv: 2504.14370 [math.CO]. URL: https://arxiv.org/abs/2504.14370 (cit. on pp. 4, 16, 24). Jon Kleinberg and Fan Wei. “Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations”. In: Proceedings of the 58th Annual ACM Symposium on Theory of Computing. STOC 2026. 2026. arXiv: 2511.05295. URL: https://arxiv.org/abs/2511.05295 (cit. on pp. 4, 16). Nick Littlestone. “Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm”. In: Machine Learning 2.4 (1988), pp. 285–318. URL: https://doi.org/10. 1007/BF00116827 (cit. on p. 1). Jiaxun Li, Vinod Raman, and Ambuj Tewari. “Generation through the lens of learning theory”. In: The Thirty Eighth Annual Conference on Learning Theory, 30-4 July 2025, Lyon, France. Vol. 291. Proceedings of Machine Learning Research. PMLR, 2025, pp. 4740–4776. URL: https: //proceedings.mlr.press/v291/raman25a.html (cit. on pp. 1–4, 7, 9). Xuechen Li, Florian Tramèr, Percy Liang, and Tatsunori Hashimoto. “Large Language Models Can Be Strong Differentially Private Learners”. In: The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URL : https://openreview.net/forum?id=bVuP3ltATMz (cit. on p. 1).

[Mir17]

[MRTZ18]

[MT07]

[MVYZ25]

[PAK19]

[PRR25]

[PSV26]

[RR25] [SMML+25]

[YNBG+24]

[Zho26]

[ZZME+25]

Ilya Mironov. “Rényi Differential Privacy”. In: 30th IEEE Computer Security Foundations Symposium, CSF 2017, Santa Barbara, CA, USA, August 21-25, 2017. IEEE Computer Society, 2017, pp. 263–275. URL: https://doi.org/10.1109/CSF.2017.11 (cit. on p. 16). H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. “Learning Differentially Private Recurrent Language Models”. In: 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL: https://openreview.net/forum?id=BJ0hF1Z0b (cit. on p. 1). Frank McSherry and Kunal Talwar. “Mechanism Design via Differential Privacy”. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). 2007, pp. 94–103 (cit. on pp. 6, 23). Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. Language Generation with Infinite Contamination. 2025. arXiv: 2511.07417 [stat.ML]. URL: https://arxiv.org/ abs/2511.07417 (cit. on pp. 4, 6, 24). Victor Perrier, Hassan Jameel Asghar, and Dali Kaafar. “Private Continual Release of RealValued Data Streams”. In: 26th Annual Network and Distributed System Security Symposium, NDSS 2019, San Diego, California, USA, February 24-27, 2019. The Internet Society, 2019. URL : https://www.ndss- symposium.org/ndss- paper/private- continualrelease-of-real-valued-data-streams/ (cit. on p. 5). Charlotte Peale, Vinod Raman, and Omer Reingold. “Representative Language Generation”. In: Forty-second International Conference on Machine Learning. 2025 (cit. on pp. 4, 16, 24). Binghui Peng, Amin Saberi, and Grigoris Velegkas. “Language Identification in the Limit with Computational Trace”. In: The Fourteenth International Conference on Learning Representations. 2026. URL: https://openreview.net/forum?id=1OAGf7ntSE (cit. on p. 24). Ananth Raman and Vinod Raman. “Generation from Noisy Examples”. In: Forty-second International Conference on Machine Learning. 2025 (cit. on pp. 1, 4, 24). Amer Sinha, Thomas Mesnard, Ryan McKenna, Daogao Liu, Christopher A ChoquetteChoo, Yangsibo Huang, Da Yu, George Kaissis, Zachary Charles, Ruibo Liu, et al. “Vaultgemma: A differentially private gemma model”. In: arXiv preprint arXiv:2510.15001 (2025) (cit. on p. 1). Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A. Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishuai Zhang. “Differentially Private Fine-tuning of Language Models”. In: J. Priv. Confidentiality 14.2 (2024). URL: https://doi.org/10.29012/jpc.880 (cit. on p. 1). Felix Zhou. “Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling”. In: 2026 SIAM Symposium on Simplicity in Algorithms (SOSA). SIAM. 2026, pp. 170–191 (cit. on p. 7). Felix Zhou, Samson Zhou, Vahab Mirrokni, Alessandro Epasto, and Vincent Cohen-Addad. “Private Training & Data Generation by Clustering Embeddings”. In: arXiv preprint arXiv:2506.16661 (2025) (cit. on p. 1).

Additional Preliminaries

In this section, we present some additional preliminaries.

A.1

Characterization of Language Identification in the Limit

Angluin [Ang80] provided a condition that characterizes the subset of countable collections which are identifiable in the limit. Informally, a collection satisfies Angluin’s condition if for any language L ∈ L , there exists a finite subset TL (called a tell-tale set) that serves as a finite “fingerprint” allowing one to distinguish L from any other language that contains TL . Definition 6 (Angluin’s Condition [Ang80]). Fix a language collection L = { L1 , L2 , . . . }. The collection L is said to satisfy Angluin’s condition if for any index i, there is a tell-tale, i.e., a finite set of strings Ti such that Ti is a subset of Li , i.e., Ti ⊆ Li , and the following holds: For all j ≥ 1, if L j ⊇ Ti , then L j is not a proper subset of Li . Roughly, this condition ensures that after observing enough examples from the target language, one can rule out all incorrect languages. The main result of Angluin [Ang80] is as follows: Theorem A.1 (Characterization of Identification in the Limit [Ang80]). The following holds for any countable collection of languages L . 1. L is identifiable in the limit if it satisfies Angluin’s condition and one has access to the tell-tale oracle. 2. If there is an algorithm that identifies L in the limit, then Angluin’s condition is true and the tell-tale oracle can be implemented. The above tight characterization shows that language identification is information-theoretically impossible even for simple collections of languages, such as the collection of all regular languages. Crucially, access to the tell-tale oracle is necessary for identification in the limit (its existence alone is not sufficient); see Theorem 2 in [Ang80].

A.2

Stochastic Identification in the Limit

In this section, we formally define language identification in the limit in a stochastic setting. Definition 7 (Stochastic Identification in the Limit). Fix a collection L = { L1 , L2 , . . . }. An adversary chooses an unknown target language K ∈ L and a distribution D supported on K. At each step n, the identification algorithm I observes x1 , . . . , xn ∼i.i.d. D and outputs an index in as its current guess for the target. We say that I identifies K in the limit if there is a time n⋆ after which it never changes its mind and its stabilized guess is correct: for all n ≥ n⋆ we have in = in⋆ and Lin = K. The collection L is identifiable in the limit if there exists an identification algorithm that succeeds for every K ∈ L and every distribution D supported on K.

Remark A.2 (Achieving Identification with Randomness). Gold’s model of language identification in the limit requires the learner to eventually stabilize on a single correct index i⋆ . At first glance, this is in tension with differential privacy, since any non-trivial DP learner must randomize and therefore outputs an incorrect index with positive probability. This, however, can be resolved: it suffices to ensure that the probability of outputting an incorrect index at round n is summable over n. The Borel–Cantelli lemma then implies that, with probability 1, only finitely many incorrect outputs occur, so the learner stabilizes to the correct index outside a null event.

A.3

Borel–Cantelli Lemma

Next, we present a well-known result due to Borel and Cantelli which is useful for ensuring our private algorithms only make a finite number of “mistakes” with probability 1. Lemma A.3 (First Borel–Cantelli Lemma). Let {En }n∈N be a sequence of events. If ∑n∈N Pr[En ] < ∞, then the probability that infinitely many of them occur is 0, that is Pr [lim supn→∞ En ] = 0. The previous result has a partial converse, which we omit here as we do not need it.

A.4

Privacy Tools

Some useful properties of DP include composition, post-processing, and group privacy. Proposition A.4 (Simple Composition; Dwork and Roth [DR14]). Let M1 : X∗ → Y, M2 : X∗ × Y → Z be ε 1 -DP and ε 2 -DP, respectively. Then the composition M2 (·, M1 (·)) : X∗ → Z is (ε 1 + ε 2 )-DP. Proposition A.5 (Post-Processing; Dwork and Roth [DR14]). Let M : X∗ → Y be ε-DP and f : Y → Z be any data-independent function. Then f ( M(·)) : X∗ → Z is ε-DP. Proposition A.6 (Group Privacy; Dwork and Roth [DR14]). Let M : X∗ → Y be ε-DP. For all datasets X, X ′ that differ by at most k ≥ 1 elements, and all measurable events E ⊆ ∆ (Y), Pr M ( X ) ∈ E ≤ ekε · Pr M ( X ′ ) ∈ E . One of the most ubiquitous tools for pure DP is the exponential mechanism. Theorem A.7 (Exponential Mechanism; McSherry and Talwar [MT07]). Let R be a collection of elements and u : X∗ × R → R a score function with sensitivity ∆u across neighboring datasets. Then the fol lowing exponential mechanism preserves ε-DP: select an element r ∈ R with probability ∝ exp

ε·u( X,r ) 2∆u

In fact, the standard Laplace mechanism for numerical queries can be viewed as a special case of the exponential mechanism. Proposition A.8 (Laplace Mechanism; Dwork and Roth [DR14]). Let f : X∗ → R be a numerical query with sensitivity ∆ f across neighboring datasets. Then the Laplace mechanism, which outputs f ( X ) + Lap(∆ f /ε), preserves ε-DP.

Additional Related Work

Below we overview some additional works related to generation in the limit [KM24] • Robustness to Noise: While the model of Kleinberg and Mullainathan [KM24] assumes that the adversary introduces no errors or omissions in the input stream, recent work has relaxed this requirement. Raman and Raman [RR25] allow the adversary to introduce a finite number of errors in the input stream and show that generation in the limit remains possible for all countable collections. Bai, Panigrahi, and Zhang [BPZ26] allow the adversary to omit elements of the target language from the stream and, as a corollary, show that all countable collections remain generatable even with an infinite number of omissions. Mehrotra, Velegkas, Yu, and Zhou [MVYZ25] extend both of these directions, considering a model where the adversary can introduce both forms of contamination (insert “noisy” elements and omit elements from the target language) and show that all countable collections remain generatable even with an infinite amount of contamination, provided the frequency of noise is “controlled.” Our private generation algorithm builds on a method of Mehrotra, Velegkas, Yu, and Zhou [MVYZ25], and interestingly inherits the same tolerance to contamination; in particular, our algorithm is both private and robust to noisy inputs and omissions. • Language Generation with Breadth: The algorithm of Kleinberg and Mullainathan [KM24] eventually outputs only in-language strings (and hence eventually stops outputting elements outside of K), but this can come at the cost of breadth—the ability to generate diverse strings from the target language. A number of works formalize breadth in different ways and show that many natural breadth requirements make generation significantly harder, in some cases approaching the difficulty of identification [CP25; KMV25; KW25; PRR25; KMV26]. Our results also connect to this direction: our identification algorithms can be converted into generation algorithms achieving these breadth notions, using our private subroutine for sampling uniformly from a language (see Lemma 4.1). In a related direction, Peng, Saberi, and Velegkas [PSV26] showed that if one has access to the computational trace of a machine that accepts the underlying language, then identification in the limit (which is perhaps the strongest notion of breadth), is achievable for all collections that are accepted by Turing Machines.

Deferred Proofs

C.1

Proof of Theorem 1.2 (Upper Bound on Sample Complexity)

Here, we prove Theorem 1.2, which says that for any collection L of k languages with closure dimension d, there exists an ε-DP algorithm in the continual release model, such that for any e ((k/ε) log (1/β)) with probability β > 0, it generates from step n∗ onward from L for n∗ = d + O at least 1 − β. First, we state the formal version of Theorem 1.2 and then prove it. Theorem C.1 (Sample Complexity Sufficient for Uniform Private Generation). Let L = { L1 , . . . , Lk } be a collection of languages with closure dimension d.

• (Continual Release DP) There is an ε-DP generation algorithm G in the continual release model such that for any m ∈ N, target language K ∈ L , and input enumeration, the time step n⋆ after which G generates from K satisfies Pr[n⋆ ≤ m] ≥ 1 − exp (−Ω ((ε/k) · (m−d)/log2 (m−d))). • (DP) There is an ε-DP generation algorithm G that, for any target language K ∈ L , given any finite set of n input elements, generates an unseen element from K with probability at least 1 − 5 exp (−ε(n−d)/(2k)). Proof of Theorem C.1. We will first give a generation algorithm that is ε-DP on a finite set of n input elements, and then use it to obtain an ε-DP generation in the continual release model. Assume that L = { L1 , . . . , Lk } is a collection of languages with closure dimension d. For a subset S ⊆ [k ] of indices, let LS = { Li : i ∈ S} denote the subcollection of languages indexed by T S. We will use Cl(LS ) = i∈S Li to denote the closure of a subcollection of languages. Upper bound for finite sample. Consider the following exponential mechanism, which assigns score to a subcollection LS given seen examples x1:n . Concretely, for any S ⊆ [k ], we set u(S, x1:n ) := |Cl(LS ) ∩ x1:n | + f (n) · |S| , where f (n) issome quantity that we will set later. We will sample LS with probability propor ε·u(S,x

)

1:n , where ∆u is the global sensitivity of u, which in this case is 1. This tional to exp 2∆u exponential mechanism is ε-pure DP. For a set S, we call it good if the index i⋆ of the target language K is contained in S, i.e., i⋆ ∈ S, and |Cl(LS )| = ∞. We call a set S bad if |Cl(LS∪{i⋆ } )| < ∞. We call a set S conservative if i⋆ ̸∈ S and |Cl(LS∪{i⋆ } )| = ∞. We note that any S falls into exactly one of the three categories above. Moreover, if S is conservative, then S ∪ {i⋆ } must be good. We will denote

ε · u(S, x1:n ) s(good) = ∑ exp , 2 good S ε · u(S, x1:n ) , s(bad) = ∑ exp 2 bad S ε · u(S, x1:n ) s(conservative) = . ∑ exp 2 conservative S

First, let us consider the bad sets. If S is bad, then |Cl(LS∪{i⋆ } )| < ∞ implies that |Cl(LS∪{i⋆ } )| ≤ d by consideration of the closure dimension. Thus, u(S, x1:n ) = |Cl(LS ) ∩ x1:n | + f (n) · |S|

= |Cl(LS ) ∩ K ∩ x1:n | + f (n) · |S| ≤ |Cl(LS∪{i⋆ } )| + f (n) · k ≤ d + k · f (n) .

Next, let us consider the good sets. We know that max u(S, x1:n ) ≥ u({i⋆ }, x1:n ) ≥ n + f (n) .

good S

Since there are at most 2k bad sets, we have ε(d + k · f (n)) ε(d + k · f (n)) k = exp + k log 2 . s(bad) ≤ 2 · exp 2 2 Since S ∪ {i⋆ } must be good if S is conservative, we have ε(|Cl(LS ) ∩ x1:n | + f (n) · |S|) s(conservative) = ∑ exp 2 conservative S ε · f (n) ε(|Cl(LS ) ∩ K ∩ x1:n | + f (n) · |S ∪ {i⋆ }|) = exp − · ∑ exp 2 2 conservative S ! ε(|Cl(LS∪{i⋆ } ) ∩ x1:n | + f (n) · |S ∪ {i⋆ }|) ε · f (n) · = exp − ∑ exp 2 2 conservative S ε · f (n) ≤ exp − · s(good) . 2

Finally, we have s(good) ≥ max exp good S

ε · u(S, x1:n ) 2

≥ exp

ε · (n + f (n)) 2

Therefore, we know that the probability of sampling a good set S using this exponential mechanism is at least s(good) s(bad) + s(conservative) + s(good) 1 ≥ ε·(n+ f (n)) ε· f (n) ε(d+k· f (n)) + k log 2 − + exp − +1 exp 2 2 2 ε(d + k · f (n)) ε · (n + f (n)) ε · f (n) ≥ 1 − exp + k log 2 − − exp − . 2 2 2 2k log 2 ε(n−d) Now we set f (n) := 1k n − d − ε , with which we get P(good) ≥ 1 − 4 exp − 2k . P(good) =

In particular, outputting Cl(LS ) where S ⊆ [k ] is sampled according to the above exponential

mechanism is ε-DP at time n, which satisfies that w.p. at least 1 − 4 exp −

ε(n−d) 2k

|Cl(LS )| = ∞ and Cl(LS ) ⊆ K . ε(n−d) By Lemma 4.1, we may choose β n = exp − 2k to obtain an element-based generator that is ε-DP at time n and outputs an element in Cl(LS ) distinct from the n input elements with proba26

ε(n−d) . Combined with the guarantee for Cl(LS ), given n distinct input bility at least 1 − exp − 2k elements x1 , . . . , xn fromK, this ε-DP generator outputs an element on ∈ K \ { x1 , ..., xn } with probability at least 1 − 5 exp −

ε(n−d) 2k

Upper bound for continual release model. Finally, we convert the above differentially private generator in the finite sample setting into a generator that is differentially private in the continual release model. To do so, for t = 1, 2, . . . , we define εt =

6 ε · π2 t 2

n t = 2t + d .

and

At each step n = nt for some t ∈ N, we apply the exponential mechanism parameter with privacy ε (n −d)

ε t to sample a set Cl(LSt ) such that with probability at least 1 − 4 exp − t 2kt

|Cl(LSt )| = ∞

, we have

Cl(LSt ) ⊆ K .

and

By Lemma 4.1, we may apply postprocessing to Cl(LSt ) to output elements in Cl(L (St )) distinct from the input all steps between nt and nt+1 − 1. This ensures that with probability at stream for ε (n −d)

. least 1 − exp − t 2kt By simple composition Proposition A.4, the total privacy budget of this algorithm in the continual release model is then at most ∞

∞

∑ ε t = π2 ∑ t 2 ≤ ε ,

t =1

and this confirms that this algorithm is ε-DP in the continual release model. By union bound, we also know that the probability that the algorithm outputs from K \ { x1 , . . . , xn } for all n ≥ nt onward is at least ε t′ ( n t′ − d ) ε t′ ( n t′ − d ) 1 − ∑ 4 exp − + exp − 2k 2k t′ ≥t ! ′ 6 ε2t ≥ 1 − 5 ∑ exp − 2 · ′2 π 2t k t′ ≥t ! ′ 3 ε 2t = 1 − 5 ∑ exp − 2 · · ′2 π k t t′ ≥t !! ε((nt − d)/ log2 (nt − d)) ≥ 1 − exp −Ω . k Since for any m ≥ d + 2, there exists t ∈ N such that nt − d ≤ m − d ≤ 2(nt − d), we conclude that for any m ∈ N, this algorithm generates from K from step n⋆ onward for some n⋆ ≤ m with

probability at least 1 − exp −Ω

ε((m − d)/ log2 (m − d)) k

!! .

This finishes the proof.

C.2

Proof of Theorem 1.3 (Lower Bound on Sample Complexity)

Here we prove Theorem 1.3, which shows the necessity of the dependency on d + k/ε for the sample complexity proved in Theorem C.1. Remark C.2 (Closure Dimension). The language collection constructed in the proof of Theorem 1.3 has closure dimension 0. Indeed, the intersection of any sub-collection of L with size ℓ is infinite if ℓ ≤ ⌊k/2⌋, or 0 otherwise. Thus, L is generatable with a single sample. We also note that we may easily incorporate the closure dimension d in our lower bound construction. The easiest way is to append a common set of d elements to all the languages in the constructed collection in Theorem 1.3. In the data sets x1:n and y1:n we construct for the proof, we will always set the first d elements in both data sets to be the d common elements of all the languages. In this way, we may show that we need n ≥ 1ε (k log 2 − O(log k )) + d, in order for an ε-DP algorithm to generate from K at time n with probability at least 2/3. Due to the above remark, without loss of generality, we can focus on the special case of Theorem 1.3 with d = 0. We first state the formal version of Theorem 1.3 (in this special case) and then prove it. Theorem C.3 (Tightness of Sample-Complexity for Uniform Private Generation). There exists a collection of k languages L = { L1 , . . . , Lk } such that for any ε-DP generation algorithm G in the continual release model (Definition 5), if the random time n⋆ such that G generates from step n⋆ onward satisfies Prn⋆ [n⋆ ≤ m] ≥ 2/3, then m ≥ 1ε (k log 2 − O(log k )). Further, without requiring privacy, there is a generation algorithm G that is guaranteed to generate from L after step n⋆ = 1. k The collection witnessing Theorem C.3 is defined in the following way. Let N = (⌊k/2 ⌋). Let us k enumerate the ⌊ /2⌋-subsets of [k ] as {S1 , S2 , . . . , S N }. Define the L as the collection consisting of Li = { j + Nt | S j ∋ i, t ∈ N} ⊆ N, for i ∈ [k ]. We remark that our lower bound in Theorem C.3 also applies to the finite sample guarantee. For the same collection of languages L = { L1 , . . . , Lk }, if an ε-DP generator A generates correctly at time n with probability at least 2/3 for any K and any enumeration, then n ≥ 1ε (k log 2 − O(log k )).

Proof of Theorem C.3. Consider the collection of languages { L1 , . . . , Lk } defined in the following k k way. Let N = (⌊k/2 ⌋). Let us enumerate the ⌊ /2⌋-subsets of [ k ] as { S1 , S2 , . . . , S N }. Define the

Algorithm 2: Data-Independent Epoch Exponential Mechanism Data: Stream of distinct elements x1 , x2 , . . . ; collection L = { Li }i≥1 ; overlaps M(k ) := max1≤a<b≤k | L a ∩ Lb | (with M (1) := 0); privacy ε > 0 Result: Continual-release hypotheses b Lt for all t ≥ 1 1 Set privacy split ε s ←

6ε for s ≥ 1 ; π2 s 2

// ∑s ε s = ε

2 Initialize epoch s ← 1; 3 Output b L1 ← L1 ; 4 for t ← 1 to ∞ do 5 6 7 8 9 10 11 12 13

15 16 17

// Initialize first output

Receive xt ; Set next release time ts ← 2s ; if t = ts then Set active search space Ws ← max {1} ∪ d ≤ s : M (d) ≤ t2s ; // Data-independent cap foreach i ∈ {1, . . . , Ws } do / Li ] ; // Error count of language i Errts (i ) ← ∑r≤ts 1[ xr ∈ us (i ) ← −Errts (i ) ; // Utility function us (i ) ≤ 0 Set sensitivity ∆ ← 1; Set temperature λs ← ε s /(2∆); 14 Sample Is ∈ {1, . . . , Ws } according to the exponential mechanism: Pr[ Is = i | X1:ts ] ∝ exp(λs us (i )); for τ ← ts to ts+1 − 1 do Output b Lτ ← L Is ; // Repeat output between releases Increment epoch s ← s + 1;

languages as Li = { j + Nt | S j ∋ i, t ∈ N} ⊆ N, for i ∈ [k ] . We will also denote LSi = { Li : i ∈ Si }. Note that by design, we have Cl(LSi ) =

\ j ∈ Si

Lj =

{ℓ + Nt | Sℓ ∋ j, t ∈ N} = {ℓ + Nt | Sℓ ⊇ Si , t ∈ N} = {i + Nt | t ∈ N} ,

j ∈ Si

where in the last equality we use the fact that {S1 , . . . , S N } is a Sperner family, i.e., Si ̸⊆ S j for any i ̸= j. Lower bound for finite sample. We will first show a stronger lower bound, that any ε-DP algorithm on a finite set of elements x1:n needs n ≥ 1ε (k log 2 − O(log k)) in order to generate from the target language with probability at least 2/3 at step n. Suppose A : N⋆ → N is an element-based generator that is ε-DP, and suppose that A generates from the target language with probability at least 2/3 at step n. Next, we proceed to show a lower bound for n. Consider the following post-processing of A. Define f : N → {1, . . . , N } as f (i ) ≡ i mod N. Note that B = f ◦ A : N⋆ → {1, . . . , N } is again ε-DP by post processing Proposition A.5. Let x1:n = { x1 , . . . , xn } be an arbitrary data set. Let j ∈ {1, . . . , N } be the minimizer of Pr( B( x1:n ) = j). Note that we have Pr( B( x1:n ) = j) ≤ 1/N . On the other hand, let us consider an alternative data set y1:n = {y1 , . . . , yn } with distinct elements such that yi ≡ j mod N for all i ∈ [n]. In other words, we have y1:n ⊆ { j + Nt | t ∈ N}. Since B is ε-DP, by Proposition A.6, we have Pr( B(y1:n ) = j) ≤ exp(nε) · Pr( B( x1:n ) = j) ≤

exp(nε) . N

(6)

Note that since y1:n ⊆ { j + Nt | t ∈ N} = Cl(LSi ) is the prefix of some valid enumeration of all languages in LSi simultaneously, for A to generate from the target language with probability at least 2/3 on the data set y1:n , its output must be in the intersection Cl(LSi ) with probability at least 2/3. Therefore, with probability at least 2/3, we have A(y1:n ) ∈ Cl(LSi ) = { j + Nt | t ∈ N}

and

B(y1:n ) = f ( A(y1:n )) = j .

Combining with (6), we get exp(nε) 2 ≤ Pr( B(y1:n ) = j) ≤ exp(nε) · Pr( B( x1:n ) = j) ≤ , 3 N and thus 1 n ≥ log ε

2 N 3

1 = log ε

2 k 1 = (k log 2 − O(log k)) . 3 ⌊k/2⌋ ε

This concludes the proof that for the constructed collection L , if an ε-DP algorithm A on a finite set x1:n of n input elements generates from K with probability at least 2/3, then n ≥ 1ε (k log 2 − O(log k )). Lower bound for continual release model. We can now easily lift our lower bound for the finite sample guarantee to the continual release model, as the latter is a stronger requirement. Suppose G is an ε-DP generation algorithm in the continual release model. If the random time n⋆ such that G generates from step n⋆ onward satisfies Pr[n⋆ ≤ m] ≥ 2/3, then in particular, G needs to generate at step m with probability at least 2/3. Moreover, since G is ε-DP in the continual release model, it is also ε-DP on a finite set x1:m of m input elements. By our lower bound for the finite sample guarantee, we have m ≥ 1ε (k log 2 − O(log k )) as desired. Next, using Theorem C.3, we may construct a countable collection L with closure dimension 0, such that for any finite n, no private algorithm can generate from L at time n with probability at least 2/3. Corollary C.4. There exists a countable language collection L with closure dimension 0, such that for any n ∈ N, no ε-DP algorithm can generate from K at time n with probability at least 2/3 for arbitrary K and enumeration of K. Thus, the difference in sample complexity between uniform private generation and uniform nonprivate generation can not only be arbitrarily large, as shown by Theorem C.3, it can also be infinite. Proof of Corollary C.4. Let Lk be the finite collection of k languages constructed in Theorem C.3. Consider the countable collection of languages L defined as L :=

{ L × { k } : L ∈ Lk } .

k ∈N

Note that any language in L is an infinite set in N2 . Moreover, since each Lk has closure dimension 0, it is clear that L also has closure dimension 0. Assume for contradiction that there exists n ∈ N and an ε-DP algorithm that generates from K at time n with probability at least 23 for arbitrary K and its enumeration. In particular, for any subcollection { L × {k } : L ∈ Lk } ⊆ L , this algorithm must generate from K at time n with probability at least 23 for arbitrary K ∈ { L × {k } : L ∈ Lk } and its enumeration. Note that this subcollection is isomorphic to Lk , and thus by Theorem C.3, we have n ≥ 1ε (k log 2 − O(log k )). Since n ≥ 1ε (k log 2 − O(log k )) must hold for arbitrary k ∈ N, we arrive at a contradiction and conclude that there is no such n ∈ N.

C.3

Proof of Theorem C.5 (Private Online Identification Upper Bound)

Theorem C.5 (Upper Bound). Let L = { L1 , L2 , . . . } be a countably infinite collection of infinite languages and ε > 0. Algorithm 2 satisfies ε-DP in the continual release model and, if L has finite pairwise intersections, identifies L in the limit in the online setting.

Proof of Theorem C.5. We prove the privacy and correctness guarantees of our algorithm separately. Privacy. Differential privacy requires the mechanism to be stable against changes in worstcase streams. We analyze the sensitivity of the utility function us (i ) at epoch s. Consider two neighboring infinite streams X and X ′ that differ in exactly one coordinate (a single replace′ ment). The prefixes X1:ts and X1:t will differ in at most one element. Therefore, the error count s ts Errts (i ) = ∑r=1 1[ xr ∈ / Li ] changes by at most 1. Thus, the global ℓ1 -sensitivity is strictly bounded by ∆ = 1. Crucially, the active search space Ws depends only on the public function M(·) and the deterministic epoch length ts . It is entirely independent of the private data stream X. Thus, restricting the domain of the exponential mechanism to Ws does not consume any privacy budget. By the standard guarantee of the exponential mechanism (Theorem A.7), the release of Is at epoch s satisfies pure ε s -DP. Because the epochs operate on nested prefixes of the same stream, we apply basic sequential composition over the infinite horizon. The total privacy cost is ∑∞ s =1 ε s = ∞ 6ε τ b ∑s=1 π2 s2 = ε. Since the intra-epoch outputs L are formed by deterministically repeating the most recently sampled Is , post-processing ensures the entire output transcript satisfies pure ε-CR-DP. Correctness. Utility is evaluated on valid stream enumerations, which by definition in the online setting contain no duplicate elements. Fix the true target language K = Li⋆ . We will show that the probability of the exponential mechanism selecting any incorrect index i ̸= i⋆ is summable over s. Because M(i⋆ ) is a finite constant and ts = 2s → ∞, there exists some epoch s1 such that for all s ≥ s1 , M (i⋆ ) ≤ ts /2 and s ≥ i⋆ . Therefore, for all s ≥ s1 , the target index satisfies the condition for the active set, meaning i⋆ ≤ Ws . Because the adversary’s stream is a valid enumeration of Li⋆ , every element xr ∈ Li⋆ . Thus, for all s, the true utility of the target is perfectly zero: us (i⋆ ) = 0. Consider any epoch s ≥ s1 and any other active candidate i ≤ Ws where i ̸= i⋆ . By the definition of the active set Ws , we are guaranteed that M(Ws ) ≤ ts /2. The maximum number of elements the candidate Li can share with the target Li⋆ is | Li⋆ ∩ Li | ≤ M (max(i⋆ , i )). Since both i⋆ ≤ Ws and i ≤ Ws , we have max(i⋆ , i ) ≤ Ws . Because M(·) is nondecreasing, | Li⋆ ∩ Li | ≤ M (Ws ) ≤ ts /2. Since the stream consists of ts distinct elements from Li⋆ , at most ts /2 of these elements can also belong to Li . Consequently, Li must be inconsistent with at least ts − ts /2 = ts /2 elements in the stream prefix. Therefore, its utility is strictly bounded: us (i ) ≤ −ts /2 = −2s−1 . For any s ≥ s1 , the probability of selecting an incorrect hypothesis is bounded by comparing the weights of all incorrect hypotheses against the weight of the true target i⋆ . Let Zs = W ∑ j=s1 exp(λs us ( j)) be the normalization factor. Since us (i⋆ ) = 0, we have Zs ≥ exp(0) = 1. Pr[ Is ̸= i⋆ | X1:ts ] =

Ws s −1 s −1 s −1 e λs u s (i ) ≤ ∑ ⋆ Zs ∑ ⋆ e−λs 2 ≤ Ws e−λs 2 ≤ se−λs 2 . i =1:i ̸=i i =1:i ̸=i

In the last step, we used the algorithmic constraint that Ws ≤ s. Substituting λs = ε s /(2∆) = π3ε 2 s2 ,

the probability of making a mistake at epoch s is bounded by: 3ε s−1 . Pr[ Is ̸= i | X1:ts ] ≤ s exp − 2 2 2 π s

⋆

Because the exponential decay inside the argument vastly overpowers the polynomial term s, this probability decays super-polynomially fast and is unconditionally summable over s. Thus, ⋆ ⋆ ∑∞ s=1 Pr[ Is ̸ = i | X1:ts ] < ∞. By the Borel–Cantelli lemma, the event { Is ̸ = i } occurs only finitely many times almost surely. Hence, there exists an epoch s0 such that Is = i⋆ for all s ≥ s0 . The algorithm makes finitely many mistakes and successfully identifies Li⋆ in the limit.

C.4

Proof of Theorem 1.6 (Private Stochastic Identification)

Algorithm 3: Private Stochastic Identification Data: Stream x1 , x2 , . . . ; collection L = { Li }i≥1 ; tell-tales { Ti }i≥1 ; prior π = (πi )i≥1 with πi > 0 and ∑i πi = 1; privacy parameter ε > 0 Result: Continual-release hypotheses b Lt for all t ≥ 1 1 Set privacy split ε s ←

6ε for s ≥ 1 ; π2 s 2

// ∑s ε s = ε

2 Initialize counts c ← 0 on X ;

// c(w) maintains ct (w) online

3 Initialize epoch s ← 1; 4 for t ← 1 to ∞ do 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Receive xt ; Update count c( xt ) ← c( xt ) + 1; Set next release time ts ← 2s ; if t = ts then Set thresholds k s ← s3 ; foreach i ≥ 1 do Errts (i ) ← ∑r≤ts 1[ xr ∈ / Li ] ; // Error count of language i Defts ,s (i ) ← ∑w∈Ti max{0, k s − c(w)} ; // Deficit count of language i us (i ) ← −Errts (i ) − Defts ,s (i ) ; // Utility function us (i ) ≤ 0 πs (i ) ← π(i ) · s−2i ; // Update base measure Set sensitivity ∆ ← 3; Set temperature λs ← ε s /(2∆); Sample Is according to the exponential mechanism with base measure πs ; Pr[ Is = i | X1:ts ] ∝ πs (i ) exp(λs us (i )); for τ ← ts to ts+1 − 1 do // Repeat output between releases Output b Lτ ← L Is ; Increment epoch s ← s + 1;

Recall that if L does not identify Angluin’s condition, then it is not identifiable even in the absence of privacy constraints. Hence, the lower bound follows immediately; we focus on obtaining the upper bound. 33

First, we establish the privacy guarantees of the algorithm by bounding the sensitivity of the utility function and composing the privacy loss across all epochs. Lemma C.6 (Privacy). For any ε > 0, Algorithm 3 appropriately parametrized is ε-differentially private in the continual release model. Proof. We analyze the privacy guarantee in three steps: bounding the global sensitivity of the utility function, establishing the privacy of each individual epoch, and composing the privacy loss across the infinite stream. Step 1: Global sensitivity of the utility function. Consider two neighboring stream prefixes X1:ts ′ and X1:t that differ in exactly one element (representing a single replacement). We analyze the s maximum effect this replacement can have on the utility us (i ) = −Errts (i ) − Defts ,s (i ). Replacing one element changes the error count Errts (i ) = ∑r≤ts 1[ xr ∈ / Li ] by at most 1. For the deficit term Defts ,s (i ) = ∑w∈Ti max{0, k s − c(w)}, replacing an element decreases the frequency count of one symbol by 1 and increases the count of another by 1. Because the function c 7→ max{0, k s − c} is 1-Lipschitz, the deficit sum changes by at most 1 + 1 = 2. By the triangle inequality, the global sensitivity of us (i ) is bounded by ∆ = 1 + 2 = 3. Step 2: Epoch-level privacy. At the end of each epoch s, the algorithm selects an index Is via the exponential mechanism, sampling proportional to πs (i ) exp(λs us (i )). The time-dependent base measure πs (i ) := πi s−2i depends only on the public prior π and the deterministic epoch index s; it is entirely independent of the private data stream. Therefore, modifying the base measure dynamically does not consume any privacy budget. By setting the temperature parameter to λs = ε s /(2∆), the standard guarantee of the exponential mechanism (Theorem A.7) ensures ε s DP. Step 3: Continual release via composition. Fix an arbitrary time horizon T ∈ N. The continuous transcript of outputs up to time T, denoted (b L1 , . . . , b L T ), is a deterministic post-processing of the finite sequence of epoch indices ( I1 , . . . , Im ), where m = max{s : ts ≤ T }. Because the algorithm processes nested prefixes of the same underlying data stream, we apply the basic composition theorem for differential privacy (Proposition A.4). The joint release of the indices ( I1 , . . . , Im ) satisfies (∑m s=1 ε s )-DP. The algorithm’s privacy budget is explicitly split such 6ε that ε s = π2 s2 . Thus, the total privacy loss over all epochs is strictly bounded by the convergent infinite series ∑∞ s=1 ε s = ε. Since the sequence of indices ( I1 , . . . , Im ) is ε-DP, and the step-by-step hypotheses b Lτ for τ ∈ [ts , ts+1 − 1] b are formed by deterministically repeating these indices ( Lτ = L Is ), the post-processing property of differential privacy (Proposition A.5) ensures that the entire output transcript satisfies ε-DP. Having established the privacy guarantees, we now shift to discussing the correctness of our approach. Fix the target index i⋆ and distribution D with supp( D ) = Li⋆ . Lemma C.7 (Correctness). For any collection of languages L that satisfies Angluin’s condition, Algorithm 3 identifies L in the limit from stochastic examples.

Proof. Fix the target index i⋆ and the target distribution D with supp( D ) = Li⋆ . We will show that the algorithm makes finitely many mistakes almost surely. Step 1: The target language eventually has zero deficit. Let the tell-tale of Li⋆ be Ti⋆ = {w1 , . . . , wm } and let p j := D (w j ) > 0. For each j, the stream count cts (w j ) follows a binomial distribution Bin(2s , p j ). Since the deficit threshold is k s = s3 , for all sufficiently large s we have k s = s3 ≤ ( p j /2)2s . By a Chernoff bound, Pr cts (w j ) < k s ≤ Pr cts (w j ) < ( p j /2) 2s ≤ exp − p j 2s /8 . Let As := {Defts ,s (i⋆ ) = 0} be the event that the target language has zero deficit at epoch s. Taking s a union bound over the finite tell-tale Ti⋆ , we have Pr[ Acs ] ≤ ∑m j=1 exp − p j 2 /8 . Because this c decays exponentially in 2s , the sum of probabilities is finite: ∑∞ s=1 Pr[ As ] < ∞. Step 2: Pointwise bounds on the exponential mechanism. Conditioned on the stream X1:ts , the exponential mechanism samples Is with probability proportional to πi s−2i exp(λs us (i )). Let Zs be the normalization factor. On the event As , the target language has perfect utility us (i⋆ ) = 0 (since ⋆ ⋆ supp( D ) = Li⋆ implies Errts (i⋆ ) = 0 always). Therefore, Zs ≥ πi⋆ s−2i exp(0) = πi⋆ s−2i . For any incorrect language i ̸= i⋆ , we can bound the conditional probability of selecting it on the event As as follows: Pr[ Is = i | X1:ts ]1 As ≤

⋆ π πi s−2i exp(λs us (i )) · 1 As = i s2(i −i) exp(λs us (i )) · 1 As . ⋆ πi ⋆ πi⋆ s−2i

(7)

To show that the algorithm eventually stops making mistakes, we will show that the sum over all epochs and all incorrect languages of the expected probability of making a mistake is finite. We split the sum over i ̸= i⋆ into the infinite tail (i > i⋆ ) and the finite prefix (i < i⋆ ). Step 3: Bounding the infinite tail (i > i⋆ ). Since utilities are always non-positive, exp(λs us (i )) ≤ ⋆ 1. For any i > i⋆ , we have i⋆ − i ≤ −1, which implies s2(i −i) ≤ s−2 . Summing (7) over all i > i⋆ yields: s −2 ∞ s −2 πi − 2 ≤ s . Pr I = i | X π = 1 ≤ [ ] 1:ts As i ∑ s ∑ π⋆ πi⋆ i∑ πi ⋆ i >i ⋆ i >i ⋆ i =1 s Taking the expectation over the stream X, the sum over all epochs s of this tail bound is ∑∞ s = 1 πi ⋆ < ∞. −2

Step 4: Bounding the finite prefix (i < i⋆ ). Since there are only finitely many such indices, we can analyze each fixed i < i⋆ individually. Taking the expectation of (7) over the stream gives: h i i πi 2 ( i ⋆ − i ) h E Pr[ Is = i | X1:ts ]1 As ≤ s E exp(λs us (i ))1 As . πi ⋆

(8)

We bound the inner expectation by considering two subcases for Li : • Case 4a: Li ̸⊇ Li⋆ . Then pi := Prx∼ D [ x ∈ / Li ] > 0, and the error is distributed as Errts (i ) ∼ Bin(2s , pi ). Since Defts ,s (i ) ≥ 0, we have us (i ) ≤ −Errts (i ). Bounding via the moment generat35

ing function of the Binomial distribution: s E[exp(λs us (i ))] ≤ E[exp(−λs Errts (i ))] = (1 − pi + pi e−λs )2 ≤ exp − pi (1 − e−λs )2s . Recall λs = ε s /(2∆) = Θ(1/s2 ). For all sufficiently large s, 1 − e−λs ≥ λs /2, meaning the expectation is bounded by exp −Ω(2s /s2 ) . • Case 4b: Li ⊋ Li⋆ . By Angluin’s condition (Definition 6), it must be that Ti ̸⊆ Li⋆ (otherwise Ti ⊆ Li⋆ ⊊ Li implies Li⋆ = Li , a contradiction). Thus, there exists some wi ∈ Ti \ Li⋆ . Because supp( D ) = Li⋆ , wi is never drawn in the stream, meaning cts (wi ) = 0 deterministically. This forces the deficit to be at least Defts ,s (i ) ≥ k s = s3 , yielding us (i ) ≤ −s3 . Thus, E[exp(λs us (i ))] ≤ exp −λs s3 = exp(−Ω(s)) . In both subcases, the expected exponential utility penalty E[exp(λs us (i ))] decays at least exponen⋆ tially fast in s. Because the leading time-penalty inversion s2(i −i) in (8) grows only polynomially, the exponential decay strictly dominates. Therefore, for each fixed i < i⋆ , the expected probability is O(e−Ω(s) ), which ishsummable over s. Since there are only finitely many i < i⋆ , their finite sum i satisfies ∑∞ s=1 ∑i <i⋆ E Pr[ Is = i | X1:ts ]1 As < ∞.

Step 5: Conclusion. By the law of total probability, we can combine the bounds from the complement event, the infinite tail, and the finite prefix to obtain the unconditional probability of an error: ∞

∞

s =1

∞

∑ Pr[ Is ̸= i⋆ ] = ∑ Pr[ Is ̸= i⋆ , Acs ] + ∑ Pr[ Is ̸= i⋆ , As ] s =1

∞

s =1

≤ ∑ Pr[ Acs ] + ∑ E ∞

=∑

s =1

Pr[ Acs ] +

∞

∑E

s =1

∑ Pr[ Is = i | X1:t ]1 A s

# s

i ̸ =i ⋆

h i ∞ Pr I = i | X 1 + E Pr I = i | X 1 [ ] [ ] s 1:ts As 1:ts As ∑ s ∑∑ #

i >i ⋆

i < i ⋆ s =1

< ∞. By the Borel–Cantelli lemma, the event { Is ̸= i⋆ } occurs only finitely many times almost surely. Hence, with probability 1, there exists some epoch s0 such that for all s ≥ s0 , Is = i⋆ . This means b Lt = K for all t ≥ ts0 , concluding the proof of identification in the limit. We now have all ingredients to prove Theorem 1.6. Proof of Theorem 1.6. First, notice that if L does not identify Angluin’s condition, it is not identifiable in the limit in the online setting [Ang80]. Moreover, identification in the limit in the online setting is equivalent to identification in the limit in the stochastic setting [Ang88]. Thus, it suffices to show the other direction.

Lemma C.6 shows that for any ε > 0, Algorithm 3 satisfies ε-DP in the continual release model. Then, Lemma C.7 shows that Algorithm 3 identifies in the limit from stochastic examples.

Record · ID 2584 · SHA-256 659a1b3e9d298779
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.