Paper deep dive
Differentially Private Language Generation and Identification in the Limit
Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 4/10/2026, 4:32:43 AM
Summary
This paper investigates the feasibility of language generation and identification in the limit under the constraint of differential privacy (DP) in the continual release model. The authors demonstrate that while language generation is possible for all countable collections of languages without qualitative loss, language identification faces fundamental barriers, specifically when languages have infinite intersections and finite set differences. The study also establishes a separation between adversarial and stochastic settings for private identification.
Entities (5)
Relation Signals (3)
Differential Privacy → prevents → Language Identification
confidence 95% · We prove that no ε-DP algorithm can identify a collection containing two languages with an infinite intersection and a finite set difference.
Stochastic Setting → enables → Language Identification
confidence 90% · We show that private identification is possible if and only if the collection is identifiable in the adversarial model.
Differential Privacy → imposescoston → Language Generation
confidence 90% · However, privacy does impose a quantitative cost: there are finite collections of size k for which uniform private generation requires Ω(k/ε) samples.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 $\varepsilon$-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 $\Omega(k/\varepsilon)$ 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 $\varepsilon$-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.
Tags
Links
- Source: https://arxiv.org/abs/2604.08504v1
- Canonical: https://arxiv.org/abs/2604.08504v1
Trouble viewing inline? Open PDF directly →
Full Text
144,019 characters extracted from source content.
Expand or collapse full text
sorting=ynt [sorting=ynt] Differentially Private Language Generation and Identification in the Limit Anay Mehrotra Grigoris Velegkas Stanford University Google Research anaymehrotra1@gmail.com gvelegkas@google.com Xifan Yu Felix Zhou Yale University Yale University xifan.yu@yale.edu felix.zhou@yale.edu Abstract We initiate the study of language generation in the limit, a model recently introduced by [KM24a], 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/ε) ( 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 2 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) 3 Model and Preliminaries 3.1 Language Generation and Identification in the Limit 3.2 Differential Privacy and Continual Release 4 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) 5 Conclusion References References 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 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) 1 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) [DMNS06a] 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., [BBDS+24a, GGKM21a, BLM20a, ALMM19a, KLNR+11a, FHMS+24a, HMST25a]), 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 [ALMM19a]. 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+21a]. 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., [SMML+25a, ZZME+25a, YNBG+24a, LTLH22a, MRTZ18a]). 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 [KM24a]. This model is motivated by classical adversarial frameworks for learning and identification [Gol67a, Lit88a], 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 ℒ=L1,L2,… L=\L_1,L_2,…\ and fixing an enumeration of K.111Formally, an enumeration of K is an infinite sequence x1,x2,…x_1,x_2,… (potentially with duplicates) such that xi∈Kx_i∈ K for all i and every x∈Kx∈ K appears at some index. At each step n≥1n≥ 1, the adversary reveals the n-th element xnx_n of the enumeration. Having observed the set of examples Sn=x1,…,xnS_n=\x_1,…,x_n\, the generator G must output a new string wn∉Snw_n∉ S_n 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∈ℒK∈ L and any enumeration of K, there exists a finite round n⋆n such that for all n≥n⋆n≥ n , the output is always correct and novel, wn∈K∖Sn.w_n∈ K S_n. This framework is rooted in Gold’s notion of identification in the limit [Gol67a], which requires the learner to identify the target language exactly. While identification is impossible for most nontrivial language collections, [KM24a] 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., [LRT25a, KMV25a, CP25a, R25a]); see Section˜1.2. Given this context, we investigate the possibility of language generation under differential privacy. 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:nx_1:n the generator outputs wnw_n, and the privacy guarantee should apply to the entire transcript of outputs. Accordingly, we adopt the continual release model of DP [DNPR10a, CSS11a], 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εe (for desired privacy value ε>0 >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 [JRSS23a, CLNS+24a, ELMZ25a]. 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 >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⋆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, [KM24a] showed that if ℒ L has finite size, then n⋆n (the time at which the generator starts generating correctly) can be upper bounded by a quantity n(ℒ)n( L) that only depends on the collection ℒ L and not on the target language K or the adversary’s enumeration. Furthermore, [LRT25a] characterized the time n⋆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, [LRT25a] showed that seeing n⋆=d+1n =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−β1-β of “success” by time n⋆n , then the analogous quantity for us is n⋆=d+O~((k/ε)⋅log(1/β))n =d+ O(( k )· ( 1β)). 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 dimension d. For any β>0β>0, the step n⋆n after which G generates satisfies n⋆≤d+O~((k/ε)log(1/β))n ≤ d+ O ( ( k ) ( 1β ) ) with probability 1−β1-β. Note that the bound on n⋆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/ε k in the sample complexity of Theorem˜1.2 is almost tight: k/ε k samples are required to achieve even a success probability of 2/3 23, as shown in our next result. Theorem 1.3 (Sample-Complexity Lower Bound; Informal; see Theorem˜C.3). For any k,d∈ℕk,d , there is a finite collection ℒ L of size k with closure dimension d such that if the time step n⋆n after which an ε -DP generation algorithm in the continual release model uniformly generates from ℒ L satisfies n⋆≤mn ≤ m with probability at least 2/3 23 independent of the target language and its enumeration, then m=d+Ω(k/ε)m=d+\, ( k ). Moreover, in the absence of privacy constraints, there is an algorithm that generates after observing d+1d+1 elements from the adversary. This shows that the dependence on d+k/ε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 one-shot ε -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+1d+1 samples, whereas with privacy, d+Θ(k/ε)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 [LRT25a] (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 [Gol67a]. In this model, an adversary similarly selects a target language K=Li⋆K=L_i from a known collection ℒ=L1,L2,… L=\L_1,L_2,…\ 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 ini_n. The algorithm identifies from ℒ L in the limit if there is a finite round n⋆n such that for all n≥n⋆n≥ n , in=i⋆i_n=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,LjL_i,L_j such that |Li∩Lj|=∞,|Li∖Lj|<∞, |L_i∩ L_j |=∞, |L_i L_j |<∞, then no ε -DP continual release algorithm (for any ε>0 >0) can identify ℒ L in the limit. In particular, if ℒ L contains two languages with Li⊆LjL_i 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 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 [Ang88a], 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 [Ang88a, KMV25a, CPT25a] 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 [KMV25a] (who, in turn, use the universal rates model by [BHMv+21a]). In this setting, the algorithm receives an i.i.d. sample of size n from a distribution supported D on some language K∈ℒ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)C· R(c· n), we say that ℒ L is generatable (respectively identifiable) at rate R.R. Notably, the constants can depend on the distribution and on ε but not the target language K∈ℒK∈ L. Informally, we can show that every countable collection (respectively every collection that satisfies Angluin’s condition [Ang80a]) 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., [KMV25a, KMV26a, CPT25a]) 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., [LRT25a, KMV25a, CP25a, R25a, PRR25a, KW25a, KW26a, HKMV25a, MVYZ25a, CPT25a, KMSV25a, CP26a, ABCK25a, AAK26a]). Perhaps the most closely related work to ours is that of [CP25a, MVYZ25a], whose algorithms we build upon. Moreover, the notion of uniform generation we explore in our work was proposed by [LRT25a]. 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. [PAK19a, FHU23a, JKRS+23a]). This includes classical estimation problems [CSS11a, CR22a, HSS23a, HUU24a], heavy hitters-related problems [CLSX12a, EMMM+23a], and lower bounds [JRSS23a, CLNS+24a, ELMZ25a]. 2 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,LjL_i,L_j with |Li∩Lj|=∞ |L_i∩ L_j |=∞ and |Li∖Lj|<∞ |L_i L_j |<∞, and assume for contradiction that some algorithm identifies Li,Lj \L_i,L_j \. Starting from an enumeration E of LiL_i, the algorithm outputs LjL_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ℓ∈ℕ \t_k_ \_ such that if we swap elements of E appropriately on these timesteps, we can (i) convert E to an enumeration E′E of LjL_j, and (i) guarantee that the algorithm cannot identify LjL_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 LjL_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 \L_1,L_2 \ with this property. For each LiL_i, maintain an error counter that is equal to the number of stream elements it misses. Then, for any adversarial stream,222This holds even if we allow each element to be repeated a constant amount of times. exactly one counter stays at zero while the other grows linearly in the limit. Now, standard continual-release techniques [DNPR10a] 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 [Ang80a]. 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 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 [MT07a]; the main technical hurdles are to (i) design appropriate score functions with low sensitivity, and (i) 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.L_i≠ 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 LiL_i with probability proportional to πt(i)⋅exp(λut(i)), _t(i)· (λ u_t(i)), where utu_t is the scoring function, πt _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 utu_t 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⊊LjL_i L_j, private (online) identification is impossible even for the two-language class Li,Lj\L_i,L_j\. In contrast, private generation is trivial in this case: since Li∩LjL_i∩ L_j is infinite, a generator can safely output elements from this intersection for infinitely many timesteps. This idea also underlies the generators of [KM24a] (and [CP25a]). Thus, a natural route is to try to use the exponential mechanism [MT07a] 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 [MVYZ25a] (inspired by [CP25a]), 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 to obtain continual-release guarantees. This is reminiscent of the lazy-updates paradigm from continual-release graph algorithms [FHO21a, ELMZ25a, DLLZ25a, Zho26a]. It remains to show that the resulting noisy priorities are accurate enough that K is included in the intersection with probability 11. Once we have computed this infinite subset U⊆KU 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 [KM24a]. Since the algorithm from the previous subsection does not exploit finiteness, we analyze a different procedure here.333Note 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. 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⊇SnL S_n. 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(ℒS≔Li:i∈S)Cl( L_S \L_i i∈ S \).444Given this closure, one can always privately post-process to sample one unseen element from it; Lemma 4.1. We will design a score function which comes with the guarantee that, as n→∞n→∞, with probability 1, the sampled subcollection ℒS L_S (P1) contains K and (P2) Cl(ℒS)Cl( L_S) is infinite. Achieving Property (P2) is straightforward: it suffices to ensure that Cl(ℒS)Cl( L_S) contains at least d+1d+1 elements, where d is the closure dimension of ℒ L. Then the definition of closure dimension implies |Cl(ℒS)|=∞ ( L_S) =∞ [LRT25a]. The main work is establishing (P1). A simple score rewards ℒS L_S proportional to how many enumerated elements lie in Cl(ℒS)Cl( L_S), 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/c1/c, where c is the number of supersets of K in ℒ L. One could repeat the exponential mechanism tnt_n times to amplify probability of sampling K, but this would require tn→∞t_n→∞ 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∉ℒSK∉ L_S, 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. 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 [HT10a]. This framework proceeds roughly as follows. Let M:→[]M: X^n→[N] be an ε -DP mechanism with discrete output space [N][N] and suppose that every v∈[N]v∈[N] is the unique correct answer to M(X′)M(X ) for some X′∈X ∈ X^n. For any dataset X∈X∈ X^n, there must be at least one output v∈[N]v∈[N] such that Pr[M(X)=v]≤1/N [M(X)=v]≤ 1N. By assumption, there is some X′∈X ∈ X^n where Pr[M(X′)=v]≥2/3 [M(X )=v]≥ 23 since v is the uniquely correct response for dataset X′X . By the definition of DP, 2/3≤Pr[M(X′)=v]≤enε⋅Pr[M(X)=v]≤enε/N. 23≤ [M(X )=v]≤ e^n · [M(X)=v]≤ e^n N\,. In other words, n≥Ω((logN)/ε)n≥ ( ( N) ). In our lower bound construction, by an appropriate postprocessing we may take the relevant output space to be a subset of the 2k2^k index sets I⊆[k]I [k], each encoding an infinite intersection ⋂i∈ILi _i∈ IL_i 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 length n. We do so via a Sperner family, which provides N=Ω~(2k)N= (2^k) distinct responses and thus gives the desired lower bound. 3 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\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 ℒ=L1,L2,… L= \L_1,L_2,… \. We define a generating algorithm =(n)n∈ℕ G=( G_n)_n as a sequence of (possibly randomized) mappings n:n→2 G_n \! X^n→ 2 X parametrized by the input size n. In words, the generator maps a finite training set to a (potentially infinite)555This is to align with the set-based and element-based notions of generations that have been considered in the literature. 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 [KM24a], which handles randomized generators as necessary for DP. Definition 1 (Language Generation in the Limit [KM24a]). Let ℒ=L1,L2,… L=\L_1,L_2,…\ be a collection of languages, =(n) G~= ( G_n ) be a generating algorithm, and K∈ℒ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⋆n≥ n , the algorithm’s output satisfies n(Sn)⊆(K∖Sn) G_n(S_n) (K S_n ), where SnS_n 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∈ℒ.K∈ L. We remark that [KM24a] originally studied deterministic generation algorithms; follow-up works studied this natural randomized version, whose analogue has also been studied for identification [Ang88a, KMV25a, CPT25a]. To gain some intuition about Definition˜1, consider the universe =Σ∗ X= ^* and the countable collection of length-threshold languages ℒ=L1,L2,… L=\L_1,L_2,…\ where Lℓ=x∈Σ∗:|x|≥ℓL_ =\x∈ ^*:|x|≥ \. Suppose the target language is K=Lℓ∗K=L_ ^* for some unknown ℓ∗∈ℕ ^* , and the adversary enumerates K as x1,x2,…x_1,x_2,…. After observing Sn=x1,…,xnS_n=\x_1,…,x_n\, we must have ℓ∗≤minx∈Sn|x| ^*≤ _x∈ S_n|x|. Hence every string of length strictly greater than minx∈Sn|x| _x∈ S_n|x| lies in every candidate language consistent with SnS_n, and in particular lies in K. A valid generator is therefore: for n≥1n≥ 1, let mn=minx∈Sn|x|m_n= _x∈ S_n|x| and output the lexicographically smallest string y∈Σmn+1y∈ ^m_n+1 with y∉Sny∉ S_n. 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 [LRT25a]). Let ℒ L be a language collection. The closure of ℒ L, denoted as Cl(ℒ)Cl( L), is the intersection of all the languages in ℒ L, i.e., Cl(ℒ)≔⋂L∈ℒLCl( L) _L∈ LL. The closure dimension of collection ℒ L is the smallest d∈−1∪ℕd∈\-1\ such that for any subcollection ℒ′⊆ℒ L L of languages, either |Cl(ℒ′)|=∞ ( L ) =∞, or |Cl(ℒ′)|≤d ( L ) ≤ d. Throughout this paper, we allow our algorithms access to the languages in the form of a membership oracle: for every i∈ℕi and x∈x∈ X, we can decide whether x∈Lix∈ L_i. 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 [Gol67a]). Fix a collection ℒ=L1,L2,… L=\L_1,L_2,…\. An adversary chooses an unknown target language K∈ℒK∈ L and enumerates its strings as x1,x2,…x_1,x_2,… (ensuring that every x∈Kx∈ K appears at some time). At each step n, the identification algorithm ℐI observes x1,…,xnx_1,…,x_n and outputs an index ini_n as its current guess for the target. We say that ℐI identifies K in the limit if there is a time n⋆n after which it never changes its mind and its stabilized guess is correct: for all n≥n⋆n≥ n we have in=in⋆i_n=i_n and Lin=KL_i_n=K. The collection ℒ L is identifiable in the limit if there exists an identification algorithm that succeeds for every K∈ℒK∈ L and every enumeration. Identification is a strictly stronger requirement than generation and is achievable only for restricted collections. [Ang80a] 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 [Ang88a] and studied by several follow-up works. Here, the adversary chooses some target K∈ℒK∈ L and some distribution D with supp(D)=K.supp(D)=K. Then, in every timestep t∈ℕt 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)∈ℒ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∈ℒK∈ L and every D with supp(D)=K,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, [Ang88a] 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 [DMNS06a] 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′∈X,X ∈ X^n (for n∈ℕn ) are neighboring if they differ in exactly one coordinate. Fix an ε>0 >0. A (randomized) algorithm n:→Δ() G_n X^n→ ( X ) is ε -DP if for all neighboring datasets X and X′X and all measurable events ℰ⊆Δ() E ( X ), Pr[n(X)∈ℰ]≤ℯε⋅Pr[(′)∈ℰ]. \! [ G_n(X)∈ E ]≤ e · \! [ G_n(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 [DNPR10a, CSS11a] model of differential privacy. Definition 5 (Continual Release). Two streams (sequences) of strings x1:n,x1:n′∈x_1:n,x_1:n ∈ X^n (for n∈ℕ∪∞n ∪\∞\) are neighboring if they differ at exactly one timestep. Fix an ε>0 >0. A (randomized) algorithm n:→Δ() G_n X^n→ ( X )^n that outputs a distribution Δ()i ( X )_i after observing x1:ix_1:i (i∈[n]i∈[n]) is ε -DP if for all neighboring streams x1:nx_1:n and x1:n′x_1:n and all measurable events ℰ⊆Δ() E ( X )^n, Pr[n(x1:n)∈ℰ]≤ℯε⋅Pr[(1:′)∈ℰ]. \! [ G_n(x_1:n)∈ E ]≤ e · \! [ G_n(x_1:n )∈ E ]. 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. 4 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⊆KU_n K of the target language K for all n≥n⋆n≥ n . Then for any sequence of failure probabilities βn∈(0,1) _n∈(0,1), there is a data-oblivious postprocessing M∘M G that is ε -DP in the continual release model and outputs an unseen element wn∈Un∖(x1:n∪w1:n−1)w_n∈ U_n (x_1:n∪ w_1:n-1) from Un⊆KU_n K at each n≥n⋆n≥ n with probability 1−βn1- _n. Proof of Lemma˜4.1. At each time step n∈ℕn , M simply extracts a finite subset Vn⊆UnV_n U_n of size |Vn|=2nβn V_n = 2n _n and samples a uniform random string from VnV_n. Since |x1:n∪w1:n−1|≤2n x_1:n∪ w_1:n-1 ≤ 2n, this avoids one of the observed strings with probability 1−βn1- _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 r~i,t r_i,t. This occurs at sparse steps tk=k6t_k=k^6 for k∈ℕk , where it computes the vector of true counts q(k)≔(r1,tk,…,rk,tk)q^(k) (r_1,t_k,…,r_k,t_k) and adds independent Laplace noise Lap(bk) Lap(b_k) to each coordinate, where bk≔tk1/3/ε0=k3/ε0b_k t_k^1/3 _0= k^3 _0. Consider two neighboring streams x1:∞,x1:∞′x_1:∞,x_1:∞ differing in exactly one element xτx_τ. For any specific step tkt_k, the L1L_1-sensitivity of the vector query q(k)q^(k) is bounded by Δ1(q(k))=∑i=1k|ri,tk(D)−ri,tk(D′)|≤k, _1(q^(k))= _i=1^k |r_i,t_k(D)-r_i,t_k(D ) |≤ k, as removing or changing one element can change the set difference x1:tk∖Lix_1:t_k L_i by at most 1 element for each language LiL_i. By simple composition of differential privacy (Proposition˜A.4), the total privacy loss is εtotal=∑k=1∞Δ1(q(k))bk=∑k=1∞k3/ε0=ε0∑k=1∞1k2=ε0⋅π26=ε. _total= _k=1^∞ _1(q^(k))b_k= _k=1^∞ kk^3/ _0= _0 _k=1^∞ 1k^2= _0· ^26= . 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⋆K=L_i . Li⋆L_i is consistent with the input stream. Intuitively, we show that (1) Li⋆L_i maintains a bounded priority score, and (2) any language LjL_j with “high error” will eventually have a priority score larger than Li⋆L_i . Define the “bad” event at step tk=k6t_k=k^6 for language i≤ki≤ k as the noise overwhelming the signal: Ei,k=|r~i,tk−ri,tk|≥tk200i2.E_i,k= \ | r_i,t_k-r_i,t_k |≥ t_k200i^2 \. Using the tail bound for Lap(bk) Lap(b_k), observing tk/bk=k6/(k3/ε0)=ε0k3t_k/b_k=k^6/(k^3/ _0)= _0k^3, we have: Pr[Ei,k]=e−tk/(200i2)bk=e−εk3200i2. [E_i,k]=e^- t_k/(200i^2)b_k=e^- k^3200i^2. Since i≤ki≤ k, we have k3/i2≥k^3/i^2≥ k. Thus Pr[Ei,k]≤exp(−Ω(ε0k)) [E_i,k]≤ (- ( _0k)). Summing over at most k2k^2 events indexed by k≥1k≥ 1 and 1≤i≤k1≤ i≤ k, we see the total failure probability is summable since ∑k≥1,i≤kPr[Ei,k]≤∑k≥1e−ε0k200k2<∞.Σ _k≥ 1,i≤ k [E_i,k ]≤Σ _k≥ 1e - _0k200k^2<∞. Now, by the Borel–Cantelli lemma, with probability 1, at most a finite number of bad events occur. Let k¯ k be the largest index such that some Ei,kE_i,k occurs. Such a k¯ k exists almost surely from our work above. We know that Ei,kE_i,k for k>k¯,i≤k> k,i≤ k does not occur. Conditioned on the complement of these bad events, the following hold. 1. Target Language Li⋆L_i : The true error is ri⋆,t=0r_i ,t=0. For t≥k¯6t≥ k^6, the observed noisy error is r~i⋆,t<t/200(i⋆)2 r_i ,t< t200(i )^2. The condition for incrementing the counter N~i⋆ N_i is r~i⋆,t/t>1/200(i⋆)2 r_i ,tt> 1200(i )^2. Since 1/300<1/200 1300< 1200, this condition is never met. Thus, N~i⋆ N_i stops growing, and its priority P~i⋆ P_i is bounded by a constant P⋆≥i⋆P ≥ i . 2. High Error Languages: For t≥k¯6t≥ k^6, we ensure that the following holds ri,t>1100i2 r_i,tt> 1100i^2 ⟹r~i,t>1200i2andri,t≤1300i2⟹r~i,t≤1200i2. r_i,tt> 1200i^2 r_i,tt≤ 1300i^2 r_i,tt≤ 1200i^2\,. 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. 1 Data: Stream of data elements x1,x2,…x_1,x_2,… and a language collection Lii≥1\L_i\_i≥ 1 Result: Privacy parameter ε>0 >0 2 3Initialize consistency counts N~i←0 N_i← 0 for all i; 4 5Set ε0←6ε/π2 _0←6 / ^2; 6 7for t←1t← 1 to ∞ do 8 Receive new string xtx_t and initialize counter k←⌊t1/6⌋k← t^1/6 ; 9 10 if t=k6t=k^6 then 11 for i←1i← 1 to k do 12 Compute true consistency-count ri,t←|x1:t∖Li|r_i,t← x_1:t L_i ; 13 14 Compute noisy consistency-count r~i,t←max0,ri,t+Lap(t1/3/ε0) r_i,t← \! \0,r_i,t+ Lap(t^1/3/ _0) \ 15 If noisy count is large, r~i,t/t>1/(200i2) r_i,t/t>1/(200i^2), then update consistency count N~i←N~i+1 N_i← N_i+1; 16 17 Update priority P~i←i+N~i P_i← i+ N_i; 18 19 Re-order L1,…,Lk \L_1,…,L_k \ in increasing priority, tie-breaking by index, as Lit(1),…,Lit(k)\L_i_t(1),…,L_i_t(k)\, i.e., for each j∈[k−1]j∈[k-1], ensure either P~it(j)<P~it(j+1) P_i_t(j)< P_i_t(j+1) or P~it(j)=Pit(j+1) P_i_t(j)=P_i_t(j+1) and it(j)<it(j+1)i_t(j)<i_t(j+1); 20 21 Compute maximal incremental infinite intersection Jt←maxj¯∈[k]:|∩j=1j¯Lit(j)|=∞J_t← \ j∈[k]: _j=1 jL_i_t(j) =∞\; 22 23 Compute ⋂j≤JtLit(j)=z1,z2,… _j≤ J_tL_i_t(j)=\z_1,z_2,…\ and output a uniformly random element wn∈z1,…,z200t3w_n∈\z_1,…,z_200t^3\; Algorithm 1 Private Approximate Intersection We argue that for all large enough t, languages with priority at most P⋆P (which include Li⋆L_i ) must have summable error. Indeed, the set ℒP⋆≔Li:i≤P⋆ L_P \L_i:i≤ P \ is a finite set containing Li⋆L_i . Moreover, any Lj∉ℒP⋆L_j∉ L_P will have priority P~j≥P⋆ P_j≥ P so that it will always come after Li⋆L_i . By the finiteness of ℒP⋆ L_P , for sufficiently large t, every Li∈ℒP⋆L_i∈ L_P whose error exceeds 1/100i2 1100i^2 infinitely often will have priority exceeding P⋆P . Thus eventually, every language LiL_i ordered before Li⋆L_i must have summable error at most 1/100i2 1100i^2. Let Cl(ℒ(k))Cl( L(k)) denote the intersection of all languages in ℒ(k)⊆ℒP⋆ L(k) L_P , the collection of languages ordered before Li⋆L_i at step tkt_k, including Li⋆L_i itself. If we show that |Cl(ℒ(k))|=∞ ( L(k)) =∞, we are done as the incremental intersection is guaranteed to include Li⋆L_i . Indeed, as k→∞k→∞, |Cl(ℒ(k))| ( L(k)) ≥|x1:tk∩Cl(ℒ(k))|≥tk(1−∑Li∈ℒ(k)ri,tktk)≥tk(1−∑i≥11100i2)≥tk2. ≥ x_1:t_k ( L(k)) ≥ t_k (1-Σ _L_i∈ L(k) r_i,t_kt_k )≥ t_k (1-Σ _i≥ 1 1100i^2 )≥ t_k2\,. In particular, |Cl(ℒ(k))|=∞ ( L(k)) =∞. Finally, we apply Lemma˜4.1 to see that sampling a uniform random string among a size 200t3200t^3 subset of an infinite subset of the target language repeats a seen element with summable probability 1100t2 1100t^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 >0 and β>0β>0, any countable collection ℒ L, and any target language K∈ℒK∈ L, there exists t=t(ε,β,ℒ,K)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−β1-β. Remark 4.2 (Non-Uniform Generation). Fix any ε,β>0 ,β>0, a collection ℒ L, and a target language K=Li⋆K=L_i . Using the tail bound of Laplace distribution as in utility analysis of the proof above, there exists t1=t1(ε,β,ℒ,K)t_1=t_1( ,β, L,K) such that with probability at least 1−β/21- β2, we have r~i⋆,t/t≤1100i⋆2 r_i ,tt≤ 1100i ^2 for all t≥t1t≥ t_1, in which case we have P~i⋆=i⋆+N~i⋆≤i⋆+t1 P_i =i + N_i ≤ i +t_1 and it stays fixed for all t≥t1t≥ t_1. Using the tail bound of Laplace distribution again, there exists t2=t2(ε,β,ℒ,K,t1)t_2=t_2( ,β, L,K,t_1) such that with probability at least 1−β/21- β2, we have |r~i,t/t−ri,t/t|≤1200i2 | r_i,tt- r_i,tt |≤ 1200i^2 for all i≤i⋆+t1i≤ i +t_1 and t≥t2t≥ t_2. Now, conditional on these events which take place with probability at least 1−β1-β, there exists t3=t3(ℒ,K,t1,t2)t_3=t_3( L,K,t_1,t_2) such that the target language K participates in the maximal incremental infinite intersection at step t for all t≥t3t≥ t_3. To see this, note that for t3t_3 large enough, the priority of the target language K stays fixed and satisfies P~i⋆≤i⋆+t1 P_i ≤ i +t_1, and all the languages LiL_i with indices at most i⋆+t1i +t_1 satisfy |r~i,t/t−ri,t/t|≤1200i2 | r_i,tt- r_i,tt |≤ 1200i^2. Let B:=max|Cl(ℒS)|:S⊆[i⋆+t1],|Cl(ℒS)|<∞B:= \|Cl( L_S)|:S [i +t_1],|Cl( L_S)|<∞\ denote the size of the maximum finite intersection of a subcollection of the languages with indices at most i⋆+t1i +t_1. For t>2Bt>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 the languages with priorities at most the priority of K have a finite intersection and ri,t>1100i2 r_i,tt> 1100i^2 for some “bad” language LiL_i that comes before K in the priority ordering at step t. However, in the latter case, the priority of “bad” language increments by 11, and this can only happen for a finite number of steps depending on i⋆i and t1t_1, 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 >0 and suppose for contradiction that there exists an ε -DP continual release identification algorithm A for ℒ L. Let Li,Lj∈ℒL_i,L_j∈ L be distinct such that |Li∩Lj|=∞|L_i∩ L_j|=∞ and |Li∖Lj|<∞.|L_i L_j|<∞. Set F≔Li∖Lj,F L_i L_j, m≔|F|<∞,m |F|<∞, I≔Li∩Lj,I L_i∩ L_j, and V≔Lj∖Li.V L_j L_i. If |V|<m|V|<m, swap the roles of (i,j)(i,j): since m<∞m<∞ and Li≠LjL_i≠ L_j, after possibly swapping we may assume throughout that |V|≥m(in particular, V≠∅).|V|≥ m (in particular, V≠ ). (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 streams x1:T,x1:T′x_1:T,x _1:T differ in at most k time steps, then for every event ℰE over the first T outputs, Pr[A(x)1:T∈ℰ]≤ekεPr[A(x′)1:T∈ℰ]. [A(x)_1:T ]~≤~e^k \, [A(x )_1:T ]. (2) Order X canonically. Further, enumerate F=f1,…,fmF=\f_1,…,f_m\ and I=a1,a2,…I=\a_1,a_2,…\ in canonical order and define a duplicate-free enumeration of LiL_i: E≔(f1,…,fm,a1,a2,a3,…).E (f_1,…,f_m,\ a_1,a_2,a_3,…). Since A identifies LiL_i on every (duplicate-free) enumeration, given E, with probability 11, 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|,N_j^S(T) |\t≤ T:\ A outputs index j at time t on input stream S\ |, we have Pr[NjE(T)≥T/2]→T→∞0. [N_j^E(T)≥ T/2 ] [T→∞]0. (3) Consider a canonical enumeration of V=Lj∖LiV=L_j L_i, i.e., V=u1,u2,…V=\u_1,u_2,…\. By @1, u1,…,umu_1,…,u_m exist and are distinct. Define E(0)E^(0) by replacing the first m elements of E with u1,…,umu_1,…,u_m: E(0)≔(u1,…,um,a1,a2,a3,…).E^(0) (u_1,…,u_m,\ a_1,a_2,a_3,…). Then E(0)E^(0) is duplicate-free and every element of E(0)E^(0) lies in LjL_j. Moreover, E and E(0)E^(0) differ in exactly m positions, so applying @2 to the event Nj(∞)=∞\N_j(∞)=∞\, we get that A outputs j only finitely many times almost surely on input E(0)E^(0) as well. Hence, Pr[NjE(0)(T)≥T/2]→T→∞0. [N_j^E^(0)(T)≥ T/2 ] [T→∞]0. (4) Now define δk≔e−2kεk2 _k e^-2k k^2. Hence, it holds that ∑k=1∞δkekε=∑k=1∞e−kεk2<∞. _k=1^∞ _ke^k = _k=1^∞ e^-k k^2<∞. By @4, we can choose an increasing sequence of times T1<T2<⋯T_1<T_2<·s such that for all k≥1k≥ 1, Pr[NjE(0)(Tk)≥Tk/2]≤δk. [N_j^E^(0)(T_k)≥ T_k/2 ]≤ _k. (5) We now perform an infinite sequence of single-coordinate edits at the times TkT_k that turns E(0)E^(0) into an enumeration of LjL_j, while ensuring that up to time TkT_k we changed at most k positions (so we can apply group privacy with parameter k). Let U(0)≔Lj∖Et(0):t≥1.U^(0) L_j \E^(0)_t:t≥ 1\. Concretely, U(0)U^(0) contains exactly the “still-missing” elements of V, namely U(0)=um+1,um+2,…U^(0)=\u_m+1,u_m+2,…\ (possibly empty if |V|=m|V|=m). We define inductively streams E(k)E^(k) and pools U(k)U^(k) as follows. Assume E(k−1)E^(k-1) has been defined, is duplicate-free and contains only elements in LjL_j. If U(0)=∅U^(0)= , then E(0)E^(0) already enumerates LjL_j (it contains all of V and all of I), and we may set E′≔E(0)E E^(0) and skip the subsequent steps. Otherwise, for each k≥1k≥ 1: • Let vkv_k be the smallest element of U(k−1)U^(k-1) in the canonical order. • Let yk≔ETk(k−1)y_k E^(k-1)_T_k be the element currently occupying position TkT_k. • Define E(k)E^(k) by a single replacement at time TkT_k: Et(k)E_t^(k) is vkv_k if t=Tkt=T_k and, otherwise, it is Et(k−1)E_t^(k-1). • Update the pool by reverting the insertion and deletion: U(k)≔(U(k−1)∖vk)∪yk.U^(k) (U^(k-1) \v_k\ )\ ∪\ \y_k\. Next, we prove that this maintains duplicate freeness and correctness of the pool. We claim by induction on k: 1. E(k)E^(k) is duplicate-free and Et(k)∈LjE^(k)_t∈ L_j for all t. 2. U(k)=Lj∖Et(k):t≥1U^(k)=L_j \E^(k)_t:t≥ 1\ (i.e., U(k)U^(k) is exactly the set of elements of LjL_j still missing from the current stream). This is immediate: by the inductive hypothesis, U(k−1)U^(k-1) is disjoint from the range of E(k−1)E^(k-1), so vk∉Et(k−1)v_k∉\E^(k-1)_t\ and inserting vkv_k introduces no duplicate; simultaneously we remove yky_k from the stream and add it back to the pool, preserving both disjointness and the identity U(k)=Lj∖range(E(k))U^(k)=L_j (E^(k)). Now define the limiting stream E′E as vkv_k if t=Tkt=T_k for some k and, otherwise, define it as Et(0)E_t^(0). Since the TkT_k’s are strictly increasing, each coordinate is modified at most once, so E′E is well-defined. E′E enumerates LjL_j. From the invariant U(k)=Lj∖range(E(k))U^(k)=L_j (E^(k)) and the fact that once a value is placed at coordinate TkT_k it is never changed again, we get the following dichotomy for any x∈Ljx∈ 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 yky_k) 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∈Ljx∈ 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∈Ljx∈ L_j appears in E′E at some finite index, and E′E is a duplicate-free enumeration of LjL_j. For each k, consider the event ℱk≔NjE′(Tk)≥Tk/2. F_k \N_j^E (T_k)≥ T_k/2 \. By construction, the prefixes E1:Tk′E _1:T_k and E1:Tk(0)E^(0)_1:T_k differ in exactly the k positions T1,…,TkT_1,…,T_k, hence in at most k positions. Applying group privacy @2 at horizon TkT_k and then @5 yields Pr[ℱkunder input E′]≤ekε⋅Pr[NjE(0)(Tk)≥Tk/2]≤ekεδk. [ F_k\ under input E ]\ ≤\ e^k · [N_j^E^(0)(T_k)≥ T_k/2 ]\ ≤\ e^k _k. Since ∑k≥1ekεδk<∞ _k≥ 1e^k _k<∞, the first Borel–Cantelli lemma implies that with probability 11 only finitely many events ℱk F_k occur when A is run on input E′E . However, if A identified LjL_j on the valid enumeration E′E , then with probability 11 there would exist a time τ such that A outputs j at every round t≥τt≥τ. Then for all k with Tk≥2τT_k≥ 2τ, NjE′(Tk)≥Tk−τ≥Tk/2,N_j^E (T_k)\ ≥\ T_k-τ\ ≥\ T_k/2, so ℱk F_k would occur for all sufficiently large k, and hence infinitely often, which is a contradiction. Therefore, A cannot identify LjL_j on the enumeration E′E , contradicting the assumption that A identifies ℒ L in the limit. This completes the proof. ∎ 5 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 [Ang88a], 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 [BS16a, Mir17a], exploring the interplay between privacy and breadth [KMV25a, KMV26a, CP25a, KW25a, KW26a, PRR25a], 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 [Gol67] E. Gold “Language Identification in the Limit” In Information and Control 10.5, 1967, p. 447–474 DOI: https://doi.org/10.1016/S0019-9958(67)91165-5 [Ang80] Dana Angluin “Inductive Inference of Formal Languages From Positive Data” In Information and Control 45.2, 1980, p. 117–135 DOI: https://doi.org/10.1016/S0019-9958(80)90285-5 [Ang88] Dana Angluin “Identifying Languages From Stochastic Examples” Yale University. Department of Computer Science, 1988 URL: http://w.cs.yale.edu/publications/techreports/tr614.pdf [Lit88] Nick Littlestone “Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm” In Machine Learning 2.4, 1988, p. 285–318 DOI: 10.1007/BF00116827 [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith “Calibrating Noise to Sensitivity in Private Data Analysis” In Theory of Cryptography Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, p. 265–284 [MT07] Frank McSherry and Kunal Talwar “Mechanism Design via Differential Privacy” In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), 2007, p. 94–103 DOI: 10.1109/FOCS.2007.66 [DNPR10] 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, p. 715–724 DOI: 10.1145/1806689.1806787 [HT10] 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, p. 705–714 DOI: 10.1145/1806689.1806786 [CSS11] T.-H. Chan, Elaine Shi and Dawn Song “Private and Continual Release of Statistics” In ACM Trans. Inf. Syst. Secur. 14.3, 2011, p. 26:1–26:24 DOI: 10.1145/2043621.2043626 [KLNR+11] Shiva Prasad Kasiviswanathan et al. “What Can We Learn Privately?” In SIAM Journal on Computing 40.3, 2011, p. 793–826 DOI: 10.1137/090756090 [CLSX12] T.-H. 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, p. 140–159 [DR14] Cynthia Dwork and Aaron Roth “The Algorithmic Foundations of Differential Privacy” In Found. Trends Theor. Comput. Sci. 9.3-4, 2014, p. 211–407 DOI: 10.1561/0400000042 [BS16] 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 9985, Lecture Notes in Computer Science, 2016, p. 635–658 DOI: 10.1007/978-3-662-53641-4\_24 [Mir17] 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, p. 263–275 DOI: 10.1109/CSF.2017.11 [MRTZ18] H. 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 [ALMM19] 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 Phoenix, AZ, USA: Association for Computing Machinery, 2019, p. 852–860 DOI: 10.1145/3313276.3316312 [PAK19] Victor Perrier, Hassan Jameel Asghar and Dali Kaafar “Private Continual Release of Real-Valued 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://w.ndss-symposium.org/ndss-paper/private-continual-release-of-real-valued-data-streams/ [BLM20] 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, p. 389–402 DOI: 10.1109/FOCS46700.2020.00044 [BHMv+21] Olivier Bousquet et al. “A Theory of Universal Learning” In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 Virtual, Italy: Association for Computing Machinery, 2021, p. 532–541 DOI: 10.1145/3406325.3451087 [CTWJ+21] Nicholas Carlini et al. “Extracting training data from large language models” In 30th USENIX security symposium (USENIX Security 21), 2021, p. 2633–2650 [FHO21] 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 204, LIPIcs Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 42:1–42:16 DOI: 10.4230/LIPICS.ESA.2021.42 [GGKM21] 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 Virtual, Italy: Association for Computing Machinery, 2021, p. 183–196 DOI: 10.1145/3406325.3451028 [CR22] 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 151, Proceedings of Machine Learning Research PMLR, 2022, p. 2397–2419 URL: https://proceedings.mlr.press/v151/rivera-cardoso22a.html [LTLH22] 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 [EMMM+23] Alessandro Epasto et al. “Differentially Private Continual Releases of Streaming Frequency Moment Estimations” In 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA 251, LIPIcs Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, p. 48:1–48:24 DOI: 10.4230/LIPICS.ITCS.2023.48 [FHU23] Hendrik Fichtenberger, Monika Henzinger and Jalaj Upadhyay “Constant matters: Fine-grained error bound on differentially private continual observation” In International Conference on Machine Learning, 2023, p. 10072–10092 PMLR [HSS23] 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 [JKRS+23] Palak Jain et al. “Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation” In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023 [JRSS23] 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 202, Proceedings of Machine Learning Research PMLR, 2023, p. 14654–14678 URL: https://proceedings.mlr.press/v202/jain23b.html [BBDS+24] Adam Block et al. “Oracle-Efficient Differentially Private Learning with Public Data” In Advances in Neural Information Processing Systems 37 Curran Associates, Inc., 2024, p. 113191–113233 DOI: 10.52202/079017-3597 [CLNS+24] Edith Cohen et al. “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 247, Proceedings of Machine Learning Research PMLR, 2024, p. 1200–1222 URL: https://proceedings.mlr.press/v247/cohen24b.html [FHMS+24] Simone Fioravanti et al. “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, p. 1983–2009 DOI: 10.1109/FOCS61266.2024.00119 [HUU24] 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), 2024, p. 995–1018 SIAM [KM24] Jon Kleinberg and Sendhil Mullainathan “Language generation in the limit” In Advances in Neural Information Processing Systems 37, 2024, p. 66058–66079 [YNBG+24] Da Yu et al. “Differentially Private Fine-tuning of Language Models” In J. Priv. Confidentiality 14.2, 2024 DOI: 10.29012/JPC.880 [ABCK25] Marcelo Arenas, Pablo Barceló, Luis Cofré and Alexander Kozachinskiy “Language Generation: Complexity Barriers and Implications for Learning”, 2025 arXiv: https://arxiv.org/abs/2511.05759 [CP25] 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 [CPT25] 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 [DLLZ25] Michael Dinitz, George Z Li, Quanquan C Liu and Felix Zhou “Differentially Private Matchings” In arXiv preprint arXiv:2501.00926, 2025 [ELMZ25] 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 353, LIPIcs Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 40:1–40:27 DOI: 10.4230/LIPICS.APPROX/RANDOM.2025.40 [HKMV25] 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 [HMST25] 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 291, Proceedings of Machine Learning Research PMLR, 2025, p. 5173–5213 URL: https://proceedings.mlr.press/v291/hanneke25d.html [KMV25] 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) Prague, Czech Republic: Association for Computing Machinery, 2025 URL: https://arxiv.org/abs/2411.09642 [KMSV25] 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 [KW25] Jon Kleinberg and Fan Wei “Density Measures for Language Generation” To appear. In Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025) IEEE, 2025 arXiv: https://arxiv.org/abs/2504.14370 [LRT25] 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 291, Proceedings of Machine Learning Research PMLR, 2025, p. 4740–4776 URL: https://proceedings.mlr.press/v291/raman25a.html [MVYZ25] Anay Mehrotra, Grigoris Velegkas, Xifan Yu and Felix Zhou “Language Generation with Infinite Contamination”, 2025 arXiv: https://arxiv.org/abs/2511.07417 [PRR25] Charlotte Peale, Vinod Raman and Omer Reingold “Representative Language Generation” In Forty-second International Conference on Machine Learning, 2025 [R25] Ananth Raman and Vinod Raman “Generation from Noisy Examples” In Forty-second International Conference on Machine Learning, 2025 [SMML+25] Amer Sinha et al. “Vaultgemma: A differentially private gemma model” In arXiv preprint arXiv:2510.15001, 2025 [ZZME+25] Felix Zhou et al. “Private Training & Data Generation by Clustering Embeddings” In arXiv preprint arXiv:2506.16661, 2025 [AAK26] Antonios Anastasopoulos, Giuseppe Ateniese and Evgenios M. Kornaropoulos “Safe Language Generation in the Limit”, 2026 arXiv: https://arxiv.org/abs/2601.08648 [BPZ26] 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, p. 794–816 DOI: 10.1137/1.9781611978971.31 [CP26] Moses Charikar and Chirag Pabbaraju “Pareto-optimal Non-uniform Language Generation” ALT 2026 In Proceedings of the 37th International Conference on Algorithmic Learning Theory, 2026 DOI: 10.48550/arXiv.2510.02795 [KMV26] Alkis Kalavasis, Anay Mehrotra and Grigoris Velegkas “On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability” Accepted to ALT 2026 In Proceedings of the 37th International Conference on Algorithmic Learning Theory (ALT 2026), Proceedings of Machine Learning Research, 2026 DOI: 10.48550/arXiv.2412.18530 [KW26] Jon Kleinberg and Fan Wei “Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations” STOC 2026 In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026 DOI: 10.48550/arXiv.2511.05295 [PSV26] 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 [Zho26] Felix Zhou “Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling” In 2026 SIAM Symposium on Simplicity in Algorithms (SOSA), 2026, p. 170–191 SIAM References [AAK26a] Antonios Anastasopoulos, Giuseppe Ateniese and Evgenios M. Kornaropoulos “Safe Language Generation in the Limit”, 2026 arXiv: https://arxiv.org/abs/2601.08648 [ABCK25a] Marcelo Arenas, Pablo Barceló, Luis Cofré and Alexander Kozachinskiy “Language Generation: Complexity Barriers and Implications for Learning”, 2025 arXiv: https://arxiv.org/abs/2511.05759 [ALMM19a] 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 Phoenix, AZ, USA: Association for Computing Machinery, 2019, p. 852–860 DOI: 10.1145/3313276.3316312 [Ang80a] Dana Angluin “Inductive Inference of Formal Languages From Positive Data” In Information and Control 45.2, 1980, p. 117–135 DOI: https://doi.org/10.1016/S0019-9958(80)90285-5 [Ang88a] Dana Angluin “Identifying Languages From Stochastic Examples” Yale University. Department of Computer Science, 1988 URL: http://w.cs.yale.edu/publications/techreports/tr614.pdf [BBDS+24a] Adam Block et al. “Oracle-Efficient Differentially Private Learning with Public Data” In Advances in Neural Information Processing Systems 37 Curran Associates, Inc., 2024, p. 113191–113233 DOI: 10.52202/079017-3597 [BHMv+21a] Olivier Bousquet et al. “A Theory of Universal Learning” In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 Virtual, Italy: Association for Computing Machinery, 2021, p. 532–541 DOI: 10.1145/3406325.3451087 [BLM20a] 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, p. 389–402 DOI: 10.1109/FOCS46700.2020.00044 [BPZ26a] 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, p. 794–816 DOI: 10.1137/1.9781611978971.31 [BS16a] 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 9985, Lecture Notes in Computer Science, 2016, p. 635–658 DOI: 10.1007/978-3-662-53641-4\_24 [CLNS+24a] Edith Cohen et al. “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 247, Proceedings of Machine Learning Research PMLR, 2024, p. 1200–1222 URL: https://proceedings.mlr.press/v247/cohen24b.html [CLSX12a] T.-H. 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, p. 140–159 [CP25a] 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 [CP26a] Moses Charikar and Chirag Pabbaraju “Pareto-optimal Non-uniform Language Generation” ALT 2026 In Proceedings of the 37th International Conference on Algorithmic Learning Theory, 2026 DOI: 10.48550/arXiv.2510.02795 [CPT25a] 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 [CR22a] 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 151, Proceedings of Machine Learning Research PMLR, 2022, p. 2397–2419 URL: https://proceedings.mlr.press/v151/rivera-cardoso22a.html [CSS11a] T.-H. Chan, Elaine Shi and Dawn Song “Private and Continual Release of Statistics” In ACM Trans. Inf. Syst. Secur. 14.3, 2011, p. 26:1–26:24 DOI: 10.1145/2043621.2043626 [CTWJ+21a] Nicholas Carlini et al. “Extracting training data from large language models” In 30th USENIX security symposium (USENIX Security 21), 2021, p. 2633–2650 [DLLZ25a] Michael Dinitz, George Z Li, Quanquan C Liu and Felix Zhou “Differentially Private Matchings” In arXiv preprint arXiv:2501.00926, 2025 [DMNS06a] Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith “Calibrating Noise to Sensitivity in Private Data Analysis” In Theory of Cryptography Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, p. 265–284 [DNPR10a] 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, p. 715–724 DOI: 10.1145/1806689.1806787 [DR14a] Cynthia Dwork and Aaron Roth “The Algorithmic Foundations of Differential Privacy” In Found. Trends Theor. Comput. Sci. 9.3-4, 2014, p. 211–407 DOI: 10.1561/0400000042 [ELMZ25a] 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 353, LIPIcs Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 40:1–40:27 DOI: 10.4230/LIPICS.APPROX/RANDOM.2025.40 [EMMM+23a] Alessandro Epasto et al. “Differentially Private Continual Releases of Streaming Frequency Moment Estimations” In 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA 251, LIPIcs Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, p. 48:1–48:24 DOI: 10.4230/LIPICS.ITCS.2023.48 [FHMS+24a] Simone Fioravanti et al. “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, p. 1983–2009 DOI: 10.1109/FOCS61266.2024.00119 [FHO21a] 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 204, LIPIcs Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, p. 42:1–42:16 DOI: 10.4230/LIPICS.ESA.2021.42 [FHU23a] Hendrik Fichtenberger, Monika Henzinger and Jalaj Upadhyay “Constant matters: Fine-grained error bound on differentially private continual observation” In International Conference on Machine Learning, 2023, p. 10072–10092 PMLR [GGKM21a] 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 Virtual, Italy: Association for Computing Machinery, 2021, p. 183–196 DOI: 10.1145/3406325.3451028 [Gol67a] E. Gold “Language Identification in the Limit” In Information and Control 10.5, 1967, p. 447–474 DOI: https://doi.org/10.1016/S0019-9958(67)91165-5 [HKMV25a] 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 [HMST25a] 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 291, Proceedings of Machine Learning Research PMLR, 2025, p. 5173–5213 URL: https://proceedings.mlr.press/v291/hanneke25d.html [HSS23a] 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 [HT10a] 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, p. 705–714 DOI: 10.1145/1806689.1806786 [HUU24a] 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), 2024, p. 995–1018 SIAM [JKRS+23a] Palak Jain et al. “Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation” In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023 [JRSS23a] 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 202, Proceedings of Machine Learning Research PMLR, 2023, p. 14654–14678 URL: https://proceedings.mlr.press/v202/jain23b.html [KLNR+11a] Shiva Prasad Kasiviswanathan et al. “What Can We Learn Privately?” In SIAM Journal on Computing 40.3, 2011, p. 793–826 DOI: 10.1137/090756090 [KM24a] Jon Kleinberg and Sendhil Mullainathan “Language generation in the limit” In Advances in Neural Information Processing Systems 37, 2024, p. 66058–66079 [KMSV25a] 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 [KMV25a] 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) Prague, Czech Republic: Association for Computing Machinery, 2025 URL: https://arxiv.org/abs/2411.09642 [KMV26a] Alkis Kalavasis, Anay Mehrotra and Grigoris Velegkas “On Characterizations for Language Generation: Interplay of Hallucinations, Breadth, and Stability” Accepted to ALT 2026 In Proceedings of the 37th International Conference on Algorithmic Learning Theory (ALT 2026), Proceedings of Machine Learning Research, 2026 DOI: 10.48550/arXiv.2412.18530 [KW25a] Jon Kleinberg and Fan Wei “Density Measures for Language Generation” To appear. In Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (FOCS 2025) IEEE, 2025 arXiv: https://arxiv.org/abs/2504.14370 [KW26a] Jon Kleinberg and Fan Wei “Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations” STOC 2026 In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026 DOI: 10.48550/arXiv.2511.05295 [Lit88a] Nick Littlestone “Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm” In Machine Learning 2.4, 1988, p. 285–318 DOI: 10.1007/BF00116827 [LRT25a] 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 291, Proceedings of Machine Learning Research PMLR, 2025, p. 4740–4776 URL: https://proceedings.mlr.press/v291/raman25a.html [LTLH22a] 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 [Mir17a] 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, p. 263–275 DOI: 10.1109/CSF.2017.11 [MRTZ18a] H. 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 [MT07a] Frank McSherry and Kunal Talwar “Mechanism Design via Differential Privacy” In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), 2007, p. 94–103 DOI: 10.1109/FOCS.2007.66 [MVYZ25a] Anay Mehrotra, Grigoris Velegkas, Xifan Yu and Felix Zhou “Language Generation with Infinite Contamination”, 2025 arXiv: https://arxiv.org/abs/2511.07417 [PAK19a] Victor Perrier, Hassan Jameel Asghar and Dali Kaafar “Private Continual Release of Real-Valued 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://w.ndss-symposium.org/ndss-paper/private-continual-release-of-real-valued-data-streams/ [PRR25a] Charlotte Peale, Vinod Raman and Omer Reingold “Representative Language Generation” In Forty-second International Conference on Machine Learning, 2025 [PSV26a] 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 [R25a] Ananth Raman and Vinod Raman “Generation from Noisy Examples” In Forty-second International Conference on Machine Learning, 2025 [SMML+25a] Amer Sinha et al. “Vaultgemma: A differentially private gemma model” In arXiv preprint arXiv:2510.15001, 2025 [YNBG+24a] Da Yu et al. “Differentially Private Fine-tuning of Language Models” In J. Priv. Confidentiality 14.2, 2024 DOI: 10.29012/JPC.880 [Zho26a] Felix Zhou “Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling” In 2026 SIAM Symposium on Simplicity in Algorithms (SOSA), 2026, p. 170–191 SIAM [ZZME+25a] Felix Zhou et al. “Private Training & Data Generation by Clustering Embeddings” In arXiv preprint arXiv:2506.16661, 2025 Appendix A Additional Preliminaries In this section, we present some additional preliminaries. A.1 Characterization of Language Identification in the Limit [Ang80a] 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∈ L, there exists a finite subset TLT_L (called a tell-tale set) that serves as a finite “fingerprint” allowing one to distinguish L from any other language that contains TLT_L. Definition 6 (Angluin’s Condition [Ang80a]). Fix a language collection ℒ=L1,L2,… L=\L_1,L_2,…\. 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 TiT_i such that TiT_i is a subset of LiL_i, i.e., Ti⊆LiT_i L_i, and the following holds: For all j≥1j≥ 1, if Lj⊇TiL_j T_i, then LjL_j is not a proper subset of LiL_i. Roughly, this condition ensures that after observing enough examples from the target language, one can rule out all incorrect languages. The main result of [Ang80a] is as follows: Theorem A.1 (Characterization of Identification in the Limit [Ang80a]). 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 [Ang80a]. 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 ℒ=L1,L2,… L=\L_1,L_2,…\. An adversary chooses an unknown target language K∈ℒK∈ L and a distribution D supported on K. At each step n, the identification algorithm ℐI observes x1,…,xn∼i.i.d.Dx_1,…,x_n _i.i.d.D and outputs an index ini_n as its current guess for the target. We say that ℐI identifies K in the limit if there is a time n⋆n after which it never changes its mind and its stabilized guess is correct: for all n≥n⋆n≥ n we have in=in⋆i_n=i_n and Lin=KL_i_n=K. The collection ℒ L is identifiable in the limit if there exists an identification algorithm that succeeds for every K∈ℒ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⋆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 11, 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 ℰn∈ℕ \ E_n \_n be a sequence of events. If ∑n∈ℕPr[ℰ]<∞, _n [ E_n]<∞, then the probability that infinitely many of them occur is 0, that is Pr[lim supn→∞ℰ]=0. [ _n→∞ E_n ]=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; [DR14a]). Let M1:∗→,ℳ2:∗×→M_1: X^*→ Y,M_2: X^*× Y→ Z be ε1 _1-DP and ε2 _2-DP, respectively. Then the composition M2(⋅,M1(⋅)):∗→M_2(·,M_1(·)): X^*→ Z is (ε1+ε2)( _1+ _2)-DP. Proposition A.5 (Post-Processing; [DR14a]). Let M:∗→M: X^*→ Y be ε -DP and f:→f: Y→ Z be any data-independent function. Then f(M(⋅)):∗→f(M(·)): X^*→ Z is ε -DP. Proposition A.6 (Group Privacy; [DR14a]). Let M:∗→M: X^*→ Y be ε -DP. For all datasets X,X′X,X that differ by at most k≥1k≥ 1 elements, and all measurable events ℰ⊆Δ() E ( Y ), Pr[M(X)∈ℰ]≤ℯε⋅Pr[ℳ(′)∈ℰ]. \! [M(X)∈ E ]≤ e^k · \! [M(X )∈ E ]\,. One of the most ubiquitous tools for pure DP is the exponential mechanism. Theorem A.7 (Exponential Mechanism; [MT07a]). Let R be a collection of elements and u:∗×ℛ→ℝu: X^*× R a score function with sensitivity Δu _u across neighboring datasets. Then the following exponential mechanism preserves ε -DP: select an element r∈Rr∈ R with probability ∝exp(ε⋅u(X,r)2Δu). ~ ( · 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; [DR14a]). Let f:∗→ℝf: X^* be a numerical query with sensitivity Δf _f across neighboring datasets. Then the Laplace mechanism, which outputs f(X)+Lap(Δf/ε)f(X)+ Lap( _f/ ), preserves ε -DP. Appendix B Additional Related Work Below we overview some additional works related to generation in the limit [KM24a] • Robustness to Noise: While the model of [KM24a] assumes that the adversary introduces no errors or omissions in the input stream, recent work has relaxed this requirement. [R25a] 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. [BPZ26a] 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. [MVYZ25a] 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 [MVYZ25a], 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 [KM24a] 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 [KMV25a, CP25a, KMV26a, PRR25a, KW25a]. 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, [PSV26a] 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. Appendix C 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 β>0β>0, it generates from step n∗n^* onward from ℒ L for n∗=d+O~((k/ε)log(1/β))n^*=d+ O ( ( k ) ( 1β ) ) with probability at least 1−β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 ℒ=L1,…,Lk L=\L_1,…,L_k\ 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∈ℕm , target language K∈ℒK∈ L, and input enumeration, the time step n⋆n after which G generates from K satisfies Pr[n⋆≤m]≥1−exp(−Ω((ε/k)⋅(m−d)/log2(m−d))) [n ≤ m]≥ 1- (- ( ( k )· (m-d) ^2(m-d) ) ). • (DP) There is an ε -DP generation algorithm G that, for any target language K∈ℒK∈ L, given any finite set of n input elements, generates an unseen element from K with probability at least 1−5exp(−ε(n−d)/(2k))1-5 (- (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 ℒ=L1,…,Lk L=\L_1,…,L_k\ is a collection of languages with closure dimension d. For a subset S⊆[k]S [k] of indices, let ℒS=Li:i∈S L_S=\L_i:i∈ S\ denote the subcollection of languages indexed by S. We will use Cl(ℒS)=⋂i∈SLiCl( L_S)= _i∈ SL_i 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 ℒS L_S given seen examples x1:nx_1:n. Concretely, for any S⊆[k]S [k], we set u(S,x1:n)≔|Cl(ℒS)∩x1:n|+f(n)⋅|S|, u(S,x_1:n) ( L_S)∩ x_1:n +f(n)·|S|\,, where f(n)f(n) is some quantity that we will set later. We will sample ℒS L_S with probability proportional to exp(ε⋅u(S,x1:n)2Δu) ( · u(S,x_1:n)2 u ), where Δu u is the global sensitivity of u, which in this case is 11. This exponential mechanism is ε -pure DP. For a set S, we call it good if the index i⋆i of the target language K is contained in S, i.e., i⋆∈Si ∈ S, and |Cl(ℒS)|=∞ ( L_S) =∞. We call a set S bad if |Cl(ℒS∪i⋆)|<∞ ( L_S∪\i \) <∞. We call a set S conservative if i⋆∉Si ∈ S and |Cl(ℒS∪i⋆)|=∞ ( L_S∪\i \) =∞. We note that any S falls into exactly one of the three categories above. Moreover, if S is conservative, then S∪i⋆S∪\i \ must be good. We will denote s(good) s(good) =∑good Sexp(ε⋅u(S,x1:n)2), = _good S ( · u(S,x_1:n)2 )\,, s(bad) s(bad) =∑bad Sexp(ε⋅u(S,x1:n)2), = _bad S ( · u(S,x_1:n)2 )\,, s(conservative) s(conservative) =∑conservative Sexp(ε⋅u(S,x1:n)2). = _conservative S ( · u(S,x_1:n)2 )\,. First, let us consider the bad sets. If S is bad, then |Cl(ℒS∪i⋆)|<∞ ( L_S∪\i \) <∞ implies that |Cl(ℒS∪i⋆)|≤d ( L_S∪\i \) ≤ d by consideration of the closure dimension. Thus, u(S,x1:n) u(S,x_1:n) =|Cl(ℒS)∩x1:n|+f(n)⋅|S| = ( L_S)∩ x_1:n +f(n)·|S| =|Cl(ℒS)∩K∩x1:n|+f(n)⋅|S| = ( L_S)∩ K∩ x_1:n +f(n)·|S| ≤|Cl(ℒS∪i⋆)|+f(n)⋅k ≤ ( L_S∪\i \) +f(n)· k ≤d+k⋅f(n). ≤ d+k· f(n)\,. Next, let us consider the good sets. We know that maxgood Su(S,x1:n)≥u(i⋆,x1:n) _good Su(S,x_1:n)≥ u(\i \,x_1:n) ≥n+f(n). ≥ n+f(n)\,. Since there are at most 2k2^k bad sets, we have s(bad) s(bad) ≤2k⋅exp(ε(d+k⋅f(n))2)=exp(ε(d+k⋅f(n))2+klog2). ≤ 2^k· ( (d+k· f(n))2 )= ( (d+k· f(n))2+k 2 )\,. Since S∪i⋆S∪\i \ must be good if S is conservative, we have s(conservative) s(conservative) =∑conservative Sexp(ε(|Cl(ℒS)∩x1:n|+f(n)⋅|S|)2) = _conservative S ( ( ( L_S)∩ x_1:n +f(n)· S )2 ) =exp(−ε⋅f(n)2)⋅∑conservative Sexp(ε(|Cl(ℒS)∩K∩x1:n|+f(n)⋅|S∪i⋆|)2) = (- · f(n)2 )· _conservative S ( ( ( L_S)∩ K∩ x_1:n +f(n)· S∪\i \ )2 ) =exp(−ε⋅f(n)2)⋅∑conservative Sexp(ε(|Cl(ℒS∪i⋆)∩x1:n|+f(n)⋅|S∪i⋆|)2) = (- · f(n)2 )· _conservative S ( ( ( L_S∪\i \)∩ x_1:n +f(n)· S∪\i \ )2 ) ≤exp(−ε⋅f(n)2)⋅s(good). ≤ (- · f(n)2 )· s(good)\,. Finally, we have s(good) s(good) ≥maxgood Sexp(ε⋅u(S,x1:n)2)≥exp(ε⋅(n+f(n))2). ≥ _good S ( · u(S,x_1:n)2 )≥ ( ·(n+f(n))2 )\,. Therefore, we know that the probability of sampling a good set S using this exponential mechanism is at least P(good) P(good) =s(good)s(bad)+s(conservative)+s(good) = s(good)s(bad)+s(conservative)+s(good) ≥1exp(ε(d+k⋅f(n))2+klog2−ε⋅(n+f(n))2)+exp(−ε⋅f(n)2)+1 ≥ 1 ( (d+k· f(n))2+k 2- ·(n+f(n))2 )+ (- · f(n)2 )+1 ≥1−exp(ε(d+k⋅f(n))2+klog2−ε⋅(n+f(n))2)−exp(−ε⋅f(n)2). ≥ 1- ( (d+k· f(n))2+k 2- ·(n+f(n))2 )- (- · f(n)2 )\,. Now we set f(n)≔1k(n−d−2klog2ε)f(n) 1k (n-d- 2k 2 ), with which we get P(good)≥1−4exp(−ε(n−d)2k)P(good)≥ 1-4 (- (n-d)2k ). In particular, outputting Cl(ℒS)Cl( L_S) where S⊆[k]S [k] is sampled according to the above exponential mechanism is ε -DP at time n, which satisfies that w.p. at least 1−4exp(−ε(n−d)2k)1-4 (- (n-d)2k ), |Cl(ℒS)|=∞ and Cl(ℒS)⊆K.|Cl( L_S)|=∞ and Cl( L_S) K\,. By Lemma˜4.1, we may choose βn=exp(−ε(n−d)2k) _n= (- (n-d)2k ) to obtain an element-based generator that is ε -DP at time n and outputs an element in Cl(ℒS)Cl( L_S) distinct from the n input elements with probability at least 1−exp(−ε(n−d)2k)1- (- (n-d)2k ). Combined with the guarantee for Cl(ℒS)Cl( L_S), given n distinct input elements x1,…,xnx_1,…,x_n from K, this ε -DP generator outputs an element on∈K∖x1,…,xno_n∈ K \x_1,...,x_n\ with probability at least 1−5exp(−ε(n−d)2k)1-5 (- (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,…t=1,2,…, we define εt=6π2⋅εt2andnt=2t+d. _t= 6 ^2· t^2 n_t=2^t+d\,. At each step n=ntn=n_t for some t∈ℕt , we apply the exponential mechanism with privacy parameter εt _t to sample a set Cl(ℒSt)Cl( L_S_t) such that with probability at least 1−4exp(−εt(nt−d)2k)1-4 (- _t(n_t-d)2k ), we have |Cl(ℒSt)|=∞andCl(ℒSt)⊆K. |Cl( L_S_t)|=∞ ( L_S_t) K\,. By Lemma˜4.1, we may apply postprocessing to Cl(ℒSt)Cl( L_S_t) to output elements in Cl(ℒ(St))Cl( L(S_t)) distinct from the input stream for all steps between ntn_t and nt+1−1n_t+1-1. This ensures that with probability at least 1−exp(−εt(nt−d)2k)1- (- _t(n_t-d)2k ). By simple composition Proposition˜A.4, the total privacy budget of this algorithm in the continual release model is then at most ∑t=1∞εt=6π2∑t=1∞εt2≤ε, _t=1^∞ _t= 6 ^2 _t=1^∞ t^2≤ \,, 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,…,xnK \x_1,…,x_n\ for all n≥ntn≥ n_t onward is at least 1−∑t′≥t(4exp(−εt′(nt′−d)2k)+exp(−εt′(nt′−d)2k)) 1- _t ≥ t (4 (- _t (n_t -d)2k )+ (- _t (n_t -d)2k ) ) ≥1−5∑t′≥texp(−6π2⋅ε2t′2t′2k) ≥ 1-5 _t ≥ t (- 6 ^2· 2^t 2t 2k ) =1−5∑t′≥texp(−3π2⋅εk⋅2t′t′2) =1-5 _t ≥ t (- 3 ^2· k· 2^t t 2 ) ≥1−exp(−Ω(ε((nt−d)/log2(nt−d))k)). ≥ 1- (- ( ((n_t-d)/ ^2(n_t-d))k ) )\,. Since for any m≥d+2m≥ d+2, there exists t∈ℕt such that nt−d≤m−d≤2(nt−d)n_t-d≤ m-d≤ 2(n_t-d), we conclude that for any m∈ℕm , this algorithm generates from K from step n⋆n onward for some n⋆≤mn ≤ m with probability at least 1−exp(−Ω(ε((m−d)/log2(m−d))k)). 1- (- ( ((m-d)/ ^2(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/ε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⌋ ≤ k2 , 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:nx_1:n and y1:ny_1: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ε(klog2−O(logk))+dn≥ 1 (k 2-O( k))+d, in order for an ε -DP algorithm to generate from K at time n with probability at least 2/3 23. Due to the above remark, without loss of generality, we can focus on the special case of Theorem˜1.3 with d=0d=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 ℒ=L1,…,Lk L=\L_1,…,L_k\ such that for any ε -DP generation algorithm G in the continual release model (Definition˜5), if the random time n⋆n such that G generates from step n⋆n onward satisfies Prn⋆[n⋆≤m]≥2/3 _n [n ≤ m]≥ 23, then m≥1ε(klog2−O(logk))m≥ 1 (k 2-O( k)). Further, without requiring privacy, there is a generation algorithm G that is guaranteed to generate from ℒ L after step n⋆=1n =1. The collection witnessing Theorem˜C.3 is defined in the following way. Let N=(k⌊k/2⌋)N= k k/2 . Let us enumerate the ⌊k/2⌋ k2 -subsets of [k][k] as S1,S2,…,SN\S_1,S_2,…,S_N\. Define the ℒ L as the collection consisting of Li=j+Nt|Sj∋i,t∈ℕ⊆ℕ, for i∈[k].L_i=\j+Nt\,|\,S_j i,t \ , 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 ℒ=L1,…,Lk L=\L_1,…,L_k\, if an ε -DP generator A generates correctly at time n with probability at least 2/3 23 for any K and any enumeration, then n≥1ε(klog2−O(logk))n≥ 1 (k 2-O( k)). Data: Stream of distinct elements x1,x2,…x_1,x_2,…; collection ℒ=Lii≥1 L=\L_i\_i≥ 1; overlaps M(k)≔max1≤a<b≤k|La∩Lb|M(k) _1≤ a<b≤ k|L_a∩ L_b| (with M(1)≔0M(1) 0); privacy ε>0 >0 Result: Continual-release hypotheses L^t L^t for all t≥1t≥ 1 1 Set privacy split εs←6επ2s2 _s← 6 ^2s^2 for s≥1s≥ 1 ; // ∑sεs=ε _s _s= 2 3Initialize epoch s←1s← 1; Output L^1←L1 L^1← L_1 ; // Initialize first output 4 5for t←1t← 1 to ∞ do 6 Receive xtx_t; 7 Set next release time ts←2st_s← 2^s; 8 if t=tst=t_s then Set active search space Ws←max(1∪d≤s:M(d)≤ts2)W_s← (\1\∪ \d≤ s:M(d)≤ t_s2 \ ) ; // Data-independent cap 9 foreach i∈1,…,Wsi∈\1,…,W_s\ do Errts(i)←∑r≤ts[xr∉Li]Err_t_s(i)← _r≤ t_s 1[x_r∉ L_i] ; // Error count of language i us(i)←−Errts(i)u_s(i)←-Err_t_s(i) ; // Utility function us(i)≤0u_s(i)≤ 0 10 11 Set sensitivity Δ←1 ← 1; 12 Set temperature λs←εs/(2Δ) _s← _s/(2 ); 13 Sample Is∈1,…,WsI_s∈\1,…,W_s\ according to the exponential mechanism: Pr[Is=i∣X1:ts]∝exp(λsus(i)) [I_s=i X_1:t_s] ( _su_s(i)); 14 for τ←tsτ← t_s to ts+1−1t_s+1-1 do Output L^τ←LIs L^τ← L_I_s ; // Repeat output between releases 15 16 Increment epoch s←s+1s← s+1; 17 Algorithm 2 Data-Independent Epoch Exponential Mechanism Proof of Theorem˜C.3. Consider the collection of languages L1,…,Lk\L_1,…,L_k\ defined in the following way. Let N=(k⌊k/2⌋)N= k k/2 . Let us enumerate the ⌊k/2⌋ k2 -subsets of [k][k] as S1,S2,…,SN\S_1,S_2,…,S_N\. Define the languages as Li=j+Nt|Sj∋i,t∈ℕ⊆ℕ, for i∈[k]. L_i=\j+Nt\,|\,S_j i,t \ , for i∈[k]\,. We will also denote ℒSi=Li:i∈Si L_S_i=\L_i:i∈ S_i\. Note that by design, we have Cl(ℒSi)=⋂j∈SiLj=⋂j∈Siℓ+Nt|Sℓ∋j,t∈ℕ=ℓ+Nt|Sℓ⊇Si,t∈ℕ=i+Nt|t∈ℕ, ( L_S_i)= _j∈ S_iL_j= _j∈ S_i\ +Nt\,|\,S_ j,t \=\ +Nt\,|\,S_ S_i,t \=\i+Nt\,|\,t \\,, where in the last equality we use the fact that S1,…,SN\S_1,…,S_N\ is a Sperner family, i.e., Si⊈SjS_i S_j for any i≠ji≠ 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:nx_1:n needs n≥1ε(klog2−O(logk))n≥ 1 (k 2-O( k)) in order to generate from the target language with probability at least 2/3 23 at step n. Suppose :ℕ⋆→ℕ A:N is an element-based generator that is ε -DP, and suppose that A generates from the target language with probability at least 2/3 23 at step n. Next, we proceed to show a lower bound for n. Consider the following post-processing of A. Define f:ℕ→1,…,Nf:N→\1,…,N\ as f(i)≡i mod Nf(i)≡ i mod N. Note that B=f∘:ℕ⋆→1,…,B=f A:N →\1,…,N\ is again ε -DP by post processing Proposition˜A.5. Let x1:n=x1,…,xnx_1:n=\x_1,…,x_n\ be an arbitrary data set. Let j∈1,…,Nj∈\1,…,N\ be the minimizer of Pr(B(x1:n)=j) (B(x_1:n)=j). Note that we have Pr(B(x1:n)=j)≤1/N (B(x_1:n)=j)≤ 1N. On the other hand, let us consider an alternative data set y1:n=y1,…,yny_1:n=\y_1,…,y_n\ with distinct elements such that yi≡j mod Ny_i≡ j mod N for all i∈[n]i∈[n]. In other words, we have y1:n⊆j+Nt|t∈ℕy_1:n \j+Nt\,|\,t \. 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. (B(y_1:n)=j)≤ (n )· (B(x_1:n)=j)≤ (n )N\,. (6) Note that since y1:n⊆j+Nt|t∈ℕ=Cl(ℒSi)y_1:n \j+Nt\,|\,t \=Cl( L_S_i) is the prefix of some valid enumeration of all languages in ℒSi L_S_i simultaneously, for A to generate from the target language with probability at least 2/3 23 on the data set y1:ny_1:n, its output must be in the intersection Cl(ℒSi)Cl( L_S_i) with probability at least 2/3 23. Therefore, with probability at least 2/3 23, we have A(y1:n) A(y_1:n) ∈Cl(ℒSi)=j+Nt|t∈ℕandB(y1:n)=f(A(y1:n))=j. ( L_S_i)=\j+Nt\,|\,t \ B(y_1:n)=f(A(y_1:n))=j\,. Combining with @6, we get 23≤Pr(B(y1:n)=j)≤exp(nε)⋅Pr(B(x1:n)=j)≤exp(nε)N, 23≤ (B(y_1:n)=j)≤ (n )· (B(x_1:n)=j)≤ (n )N\,, and thus n n ≥1εlog(23N)=1εlog(23(k⌊k/2⌋))=1ε(klog2−O(logk)). ≥ 1 ( 23N )= 1 ( 23 k k/2 )= 1 (k 2-O( k) )\,. This concludes the proof that for the constructed collection ℒ L, if an ε -DP algorithm A on a finite set x1:nx_1:n of n input elements generates from K with probability at least 2/3 23, then n≥1ε(klog2−O(logk))n≥ 1 (k 2-O( 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⋆n such that G generates from step n⋆n onward satisfies Pr[n⋆≤m]≥2/3 [n ≤ m]≥ 23, then in particular, G needs to generate at step m with probability at least 2/3 23. Moreover, since G is ε -DP in the continual release model, it is also ε -DP on a finite set x1:mx_1:m of m input elements. By our lower bound for the finite sample guarantee, we have m≥1ε(klog2−O(logk))m≥ 1 (k 2-O( 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 23. 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 23 for arbitrary K and enumeration of K. Thus, the difference in sample complexity between uniform private generation and uniform non-private generation can not only be arbitrarily large, as shown by Theorem˜C.3, it can also be infinite. Proof of Corollary˜C.4. Let ℒk L_k be the finite collection of k languages constructed in Theorem˜C.3. Consider the countable collection of languages ℒ L defined as ℒ≔⨆k∈ℕL×k:L∈ℒk. L _k \L×\k\:L∈ L_k \. Note that any language in ℒ L is an infinite set in ℕ2N^2. Moreover, since each ℒk L_k 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 23 for arbitrary K and its enumeration. In particular, for any subcollection L×k:L∈ℒk⊆ℒ\L×\k\:L∈ L_k\ L, this algorithm must generate from K at time n with probability at least 23 23 for arbitrary K∈L×k:L∈ℒkK∈\L×\k\:L∈ L_k\ and its enumeration. Note that this subcollection is isomorphic to ℒk L_k, and thus by Theorem˜C.3, we have n≥1ε(klog2−O(logk))n≥ 1 (k 2-O( k) ). Since n≥1ε(klog2−O(logk))n≥ 1 (k 2-O( k) ) must hold for arbitrary k∈ℕk , 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 ℒ=L1,L2,… L=\L_1,L_2,…\ be a countably infinite collection of infinite languages and ε>0 >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 worst-case streams. We analyze the sensitivity of the utility function us(i)u_s(i) at epoch s. Consider two neighboring infinite streams X and X′X that differ in exactly one coordinate (a single replacement). The prefixes X1:tsX_1:t_s and X1:ts′X _1:t_s will differ in at most one element. Therefore, the error count Errts(i)=∑r=1ts[xr∉Li]Err_t_s(i)= _r=1^t_s 1[x_r∉ L_i] changes by at most 11. Thus, the global ℓ1 _1-sensitivity is strictly bounded by Δ=1 =1. Crucially, the active search space WsW_s depends only on the public function M(⋅)M(·) and the deterministic epoch length tst_s. It is entirely independent of the private data stream X. Thus, restricting the domain of the exponential mechanism to WsW_s does not consume any privacy budget. By the standard guarantee of the exponential mechanism (Theorem˜A.7), the release of IsI_s at epoch s satisfies pure εs _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=∑s=1∞6επ2s2=ε _s=1^∞ _s= _s=1^∞ 6 ^2s^2= . Since the intra-epoch outputs L^τ L^τ are formed by deterministically repeating the most recently sampled IsI_s, 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⋆K=L_i . We will show that the probability of the exponential mechanism selecting any incorrect index i≠i⋆i≠ i is summable over s. Because M(i⋆)M(i ) is a finite constant and ts=2s→∞t_s=2^s→∞, there exists some epoch s1s_1 such that for all s≥s1s≥ s_1, M(i⋆)≤ts/2M(i )≤ t_s/2 and s≥i⋆s≥ i . Therefore, for all s≥s1s≥ s_1, the target index satisfies the condition for the active set, meaning i⋆≤Wsi ≤ W_s. Because the adversary’s stream is a valid enumeration of Li⋆L_i , every element xr∈Li⋆x_r∈ L_i . Thus, for all s, the true utility of the target is perfectly zero: us(i⋆)=0u_s(i )=0. Consider any epoch s≥s1s≥ s_1 and any other active candidate i≤Wsi≤ W_s where i≠i⋆i≠ i . By the definition of the active set WsW_s, we are guaranteed that M(Ws)≤ts/2M(W_s)≤ t_s/2. The maximum number of elements the candidate LiL_i can share with the target Li⋆L_i is |Li⋆∩Li|≤M(max(i⋆,i))|L_i ∩ L_i|≤ M( (i ,i)). Since both i⋆≤Wsi ≤ W_s and i≤Wsi≤ W_s, we have max(i⋆,i)≤Ws (i ,i)≤ W_s. Because M(⋅)M(·) is non-decreasing, |Li⋆∩Li|≤M(Ws)≤ts/2|L_i ∩ L_i|≤ M(W_s)≤ t_s/2. Since the stream consists of tst_s distinct elements from Li⋆L_i , at most ts/2t_s/2 of these elements can also belong to LiL_i. Consequently, LiL_i must be inconsistent with at least ts−ts/2=ts/2t_s-t_s/2=t_s/2 elements in the stream prefix. Therefore, its utility is strictly bounded: us(i)≤−ts/2=−2s−1u_s(i)≤-t_s/2=-2^s-1. For any s≥s1s≥ s_1, 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⋆i . Let Zs=∑j=1Wsexp(λsus(j))Z_s= _j=1^W_s ( _su_s(j)) be the normalization factor. Since us(i⋆)=0u_s(i )=0, we have Zs≥exp(0)=1Z_s≥ (0)=1. Pr[Is≠i⋆∣X1:ts] [I_s≠ i X_1:t_s] =∑i=1:i≠i⋆Wseλsus(i)Zs≤∑i=1:i≠i⋆Wse−λs2s−1≤Wse−λs2s−1≤se−λs2s−1. = _ subarrayci=1:i≠ i subarray^W_s e _su_s(i)Z_s≤ _ subarrayci=1:i≠ i subarray^W_se^- _s2^s-1≤ W_se^- _s2^s-1≤ se^- _s2^s-1\,. In the last step, we used the algorithmic constraint that Ws≤sW_s≤ s. Substituting λs=εs/(2Δ)=3επ2s2 _s= _s/(2 )= 3 ^2s^2, the probability of making a mistake at epoch s is bounded by: Pr[Is≠i⋆∣X1:ts]≤sexp(−3επ2s22s−1). [I_s≠ i X_1:t_s]≤ s (- 3 ^2s^22^s-1 ). 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]<∞ _s=1^∞ [I_s≠ i X_1:t_s]<∞. By the Borel–Cantelli lemma, the event Is≠i⋆\I_s≠ i \ occurs only finitely many times almost surely. Hence, there exists an epoch s0s_0 such that Is=i⋆I_s=i for all s≥s0s≥ s_0. The algorithm makes finitely many mistakes and successfully identifies Li⋆L_i in the limit. ∎ C.4 Proof of Theorem˜1.6 (Private Stochastic Identification) Data: Stream x1,x2,…x_1,x_2,…; collection ℒ=Lii≥1 L=\L_i\_i≥ 1; tell-tales Tii≥1\T_i\_i≥ 1; prior π=(πi)i≥1 =( _i)_i≥ 1 with πi>0 _i>0 and ∑iπi=1 _i _i=1; privacy parameter ε>0 >0 Result: Continual-release hypotheses L^t L^t for all t≥1t≥ 1 1 Set privacy split εs←6επ2s2 _s← 6 ^2s^2 for s≥1s≥ 1 ; // ∑sεs=ε _s _s= 2 Initialize counts c←0c← 0 on X ; // c(w)c(w) maintains ct(w)c_t(w) online 3 Initialize epoch s←1s← 1; 4 5for t←1t← 1 to ∞ do 6 Receive xtx_t; 7 Update count c(xt)←c(xt)+1c(x_t)← c(x_t)+1; 8 Set next release time ts←2st_s← 2^s; 9 if t=tst=t_s then 10 Set thresholds ks←s3k_s← s^3; 11 foreach i≥1i≥ 1 do Errts(i)←∑r≤ts[xr∉Li]Err_t_s(i)← _r≤ t_s 1[x_r∉ L_i] ; // Error count of language i Defts,s(i)←∑w∈Timax0,ks−c(w)Def_t_s,s(i)← _w∈ T_i \0,\,k_s-c(w)\ ; // Deficit count of language i us(i)←−Errts(i)−Defts,s(i)u_s(i)←-Err_t_s(i)-Def_t_s,s(i) ; // Utility function us(i)≤0u_s(i)≤ 0 πs(i)←π(i)⋅s−2i _s(i)← (i)· s^-2i ; // Update base measure 12 13 Set sensitivity Δ←3 ← 3; 14 Set temperature λs←εs/(2Δ) _s← _s/(2 ); 15 Sample IsI_s according to the exponential mechanism with base measure πs _s; 16 Pr[Is=i∣X1:ts]∝πs(i)exp(λsus(i)) [I_s=i X_1:t_s] _s(i) ( _su_s(i)); 17 for τ←tsτ← t_s to ts+1−1t_s+1-1 do Output L^τ←LIs L_τ← L_I_s ; // Repeat output between releases 18 19 Increment epoch s←s+1s← s+1; 20 Algorithm 3 Private Stochastic Identification 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. 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 >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:tsX_1:t_s and X1:ts′X _1:t_s that differ in exactly one element (representing a single replacement). We analyze the maximum effect this replacement can have on the utility us(i)=−Errts(i)−Defts,s(i)u_s(i)=-Err_t_s(i)-Def_t_s,s(i). Replacing one element changes the error count Errts(i)=∑r≤ts[xr∉Li]Err_t_s(i)= _r≤ t_s 1[x_r∉ L_i] by at most 11. For the deficit term Defts,s(i)=∑w∈Timax0,ks−c(w)Def_t_s,s(i)= _w∈ T_i \0,\,k_s-c(w)\, replacing an element decreases the frequency count of one symbol by 11 and increases the count of another by 11. Because the function c↦max0,ks−cc \0,k_s-c\ is 11-Lipschitz, the deficit sum changes by at most 1+1=21+1=2. By the triangle inequality, the global sensitivity of us(i)u_s(i) is bounded by Δ=1+2=3 =1+2=3. Step 2: Epoch-level privacy. At the end of each epoch s, the algorithm selects an index IsI_s via the exponential mechanism, sampling proportional to πs(i)exp(λsus(i)) _s(i) ( _su_s(i)). The time-dependent base measure πs(i)≔πis−2i _s(i) _is^-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Δ) _s= _s/(2 ), the standard guarantee of the exponential mechanism (Theorem˜A.7) ensures εs _s-DP. Step 3: Continual release via composition. Fix an arbitrary time horizon T∈ℕT . The continuous transcript of outputs up to time T, denoted (L^1,…,L^T)( L^1,…, L^T), is a deterministic post-processing of the finite sequence of epoch indices (I1,…,Im)(I_1,…,I_m), where m=maxs:ts≤Tm= \s:t_s≤ 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)(I_1,…,I_m) satisfies (∑s=1mεs)( _s=1^m _s)-DP. The algorithm’s privacy budget is explicitly split such that εs=6επ2s2 _s= 6 ^2s^2. Thus, the total privacy loss over all epochs is strictly bounded by the convergent infinite series ∑s=1∞εs=ε _s=1^∞ _s= . Since the sequence of indices (I1,…,Im)(I_1,…,I_m) is ε -DP, and the step-by-step hypotheses L^τ L_τ for τ∈[ts,ts+1−1]τ∈[t_s,t_s+1-1] are formed by deterministically repeating these indices (L^τ=LIs L_τ=L_I_s), 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⋆i and distribution D with supp(D)=Li⋆supp(D)=L_i . 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⋆i and the target distribution D with supp(D)=Li⋆supp(D)=L_i . 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⋆L_i be Ti⋆=w1,…,wmT_i =\w_1,…,w_m\ and let pj≔D(wj)>0p_j D(w_j)>0. For each j, the stream count cts(wj)c_t_s(w_j) follows a binomial distribution Bin(2s,pj)Bin(2^s,p_j). Since the deficit threshold is ks=s3k_s=s^3, for all sufficiently large s we have ks=s3≤(pj/2)2sk_s=s^3≤(p_j/2)2^s. By a Chernoff bound, Pr[cts(wj)<ks]≤Pr[cts(wj)<(pj/2) 2s]≤exp(−pj2s/8). [c_t_s(w_j)<k_s]≤ [c_t_s(w_j)<(p_j/2)\,2^s]≤ (-p_j2^s/8). Let As≔Defts,s(i⋆)=0A_s \Def_t_s,s(i )=0\ be the event that the target language has zero deficit at epoch s. Taking a union bound over the finite tell-tale Ti⋆T_i , we have Pr[Asc]≤∑j=1mexp(−pj2s/8) [A_s^c]≤ _j=1^m (-p_j2^s/8). Because this decays exponentially in 2s2^s, the sum of probabilities is finite: ∑s=1∞Pr[Asc]<∞ _s=1^∞ [A_s^c]<∞. Step 2: Pointwise bounds on the exponential mechanism. Conditioned on the stream X1:tsX_1:t_s, the exponential mechanism samples IsI_s with probability proportional to πis−2iexp(λsus(i)) _is^-2i ( _su_s(i)). Let ZsZ_s be the normalization factor. On the event AsA_s, the target language has perfect utility us(i⋆)=0u_s(i )=0 (since supp(D)=Li⋆supp(D)=L_i implies Errts(i⋆)=0Err_t_s(i )=0 always). Therefore, Zs≥πi⋆s−2i⋆exp(0)=πi⋆s−2i⋆Z_s≥ _i s^-2i (0)= _i s^-2i . For any incorrect language i≠i⋆i≠ i , we can bound the conditional probability of selecting it on the event AsA_s as follows: Pr[Is=i∣X1:ts]As [I_s=i X_1:t_s] 1_A_s ≤πis−2iexp(λsus(i))πi⋆s−2i⋆⋅As=πiπi⋆s2(i⋆−i)exp(λsus(i))⋅As. ≤ _is^-2i ( _su_s(i)) _i s^-2i · 1_A_s= _i _i s^2(i -i) ( _su_s(i))· 1_A_s\,. (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⋆i≠ i into the infinite tail (i>i⋆i>i ) and the finite prefix (i<i⋆i<i ). Step 3: Bounding the infinite tail (i>i⋆i>i ). Since utilities are always non-positive, exp(λsus(i))≤1 ( _su_s(i))≤ 1. For any i>i⋆i>i , we have i⋆−i≤−1i -i≤-1, which implies s2(i⋆−i)≤s−2s^2(i -i)≤ s^-2. Summing @7 over all i>i⋆i>i yields: ∑i>i⋆Pr[Is=i∣X1:ts]As≤∑i>i⋆πiπi⋆s−2≤s−2πi⋆∑i=1∞πi=s−2πi⋆. _i>i [I_s=i X_1:t_s] 1_A_s≤ _i>i _i _i s^-2≤ s^-2 _i _i=1^∞ _i= s^-2 _i \,. Taking the expectation over the stream X, the sum over all epochs s of this tail bound is ∑s=1∞s−2πi⋆<∞ _s=1^∞ s^-2 _i <∞. Step 4: Bounding the finite prefix (i<i⋆i<i ). Since there are only finitely many such indices, we can analyze each fixed i<i⋆i<i individually. Taking the expectation of @7 over the stream gives: [Pr[Is=i∣X1:ts]As]≤πiπi⋆s2(i⋆−i)[exp(λsus(i))As]. E [ [I_s=i X_1:t_s] 1_A_s ]≤ _i _i s^2(i -i)~~ E\! [ ( _su_s(i)) 1_A_s ]\,. (8) We bound the inner expectation by considering two subcases for LiL_i: • Case 4a: Li⊉Li⋆L_i L_i . Then pi≔Prx∼D[x∉Li]>0p_i _x D[x∉ L_i]>0, and the error is distributed as Errts(i)∼Bin(2s,pi)Err_t_s(i) (2^s,p_i). Since Defts,s(i)≥0Def_t_s,s(i)≥ 0, we have us(i)≤−Errts(i)u_s(i)≤-Err_t_s(i). Bounding via the moment generating function of the Binomial distribution: [exp(λsus(i))]≤[exp(−λsErrts(i))]=(1−pi+pie−λs)2s≤exp(−pi(1−e−λs)2s). E[ ( _su_s(i))]≤ E[ (- _sErr_t_s(i))]=(1-p_i+p_ie^- _s)^2^s≤ (-p_i(1-e^- _s)2^s). Recall λs=εs/(2Δ)=Θ(1/s2) _s= _s/(2 )= (1/s^2). For all sufficiently large s, 1−e−λs≥λs/21-e^- _s≥ _s/2, meaning the expectation is bounded by exp(−Ω(2s/s2)) (- (2^s/s^2)). • Case 4b: Li⊋Li⋆L_i L_i . By Angluin’s condition (Definition˜6), it must be that Ti⊈Li⋆T_i L_i (otherwise Ti⊆Li⋆⊊LiT_i L_i L_i implies Li⋆=LiL_i =L_i, a contradiction). Thus, there exists some wi∈Ti∖Li⋆w_i∈ T_i L_i . Because supp(D)=Li⋆supp(D)=L_i , wiw_i is never drawn in the stream, meaning cts(wi)=0c_t_s(w_i)=0 deterministically. This forces the deficit to be at least Defts,s(i)≥ks=s3Def_t_s,s(i)≥ k_s=s^3, yielding us(i)≤−s3u_s(i)≤-s^3. Thus, [exp(λsus(i))]≤exp(−λss3)=exp(−Ω(s)). E[ ( _su_s(i))]≤ (- _ss^3)= (- (s))\,. In both subcases, the expected exponential utility penalty [exp(λsus(i))] E[ ( _su_s(i))] decays at least exponentially fast in s. Because the leading time-penalty inversion s2(i⋆−i)s^2(i -i) in @8 grows only polynomially, the exponential decay strictly dominates. Therefore, for each fixed i<i⋆i<i , the expected probability is O(e−Ω(s))O(e^- (s)), which is summable over s. Since there are only finitely many i<i⋆i<i , their finite sum satisfies ∑s=1∞∑i<i⋆[Pr[Is=i∣X1:ts]As]<∞ _s=1^∞ _i<i E [ [I_s=i X_1:t_s] 1_A_s ]<∞. 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⋆] _s=1^∞ [I_s≠ i ] =∑s=1∞Pr[Is≠i⋆,Asc]+∑s=1∞Pr[Is≠i⋆,As] = _s=1^∞ [I_s≠ i ,A_s^c]+ _s=1^∞ [I_s≠ i ,A_s] ≤∑s=1∞Pr[Asc]+∑s=1∞[∑i≠i⋆Pr[Is=i∣X1:ts]As] ≤ _s=1^∞ [A_s^c]+ _s=1^∞ E [ _i≠ i [I_s=i X_1:t_s] 1_A_s ] =∑s=1∞Pr[Asc]+∑s=1∞[∑i>i⋆Pr[Is=i∣X1:ts]As]+∑i<i⋆∑s=1∞[Pr[Is=i∣X1:ts]As] = _s=1^∞ [A_s^c]+ _s=1^∞ E [ _i>i [I_s=i X_1:t_s] 1_A_s ]+ _i<i _s=1^∞ E [ [I_s=i X_1:t_s] 1_A_s ] <∞. <∞. By the Borel–Cantelli lemma, the event Is≠i⋆\I_s≠ i \ occurs only finitely many times almost surely. Hence, with probability 11, there exists some epoch s0s_0 such that for all s≥s0s≥ s_0, Is=i⋆I_s=i . This means L^t=K L^t=K for all t≥ts0t≥ t_s_0, 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 [Ang80a]. Moreover, identification in the limit in the online setting is equivalent to identification in the limit in the stochastic setting [Ang88a]. Thus, it suffices to show the other direction. Lemma˜C.6 shows that for any ε>0, >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. ∎