Conceptio › Archive › arXiv CS

arXiv CSopen access

On the Price of Privacy for Language Identification and Generation

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cryptography, security, privacy, cybersecurity

On the Price of Privacy for Language Identification and Generation Xiaoyu Li1∗

Andi Han2†

Jiaojiao Jiang1‡

arXiv:2604.07238v1 [cs.LG] 8 Apr 2026

1 University of New South Wales

Junbin Gao2§

2 University of Sydney

Abstract As large language models (LLMs) are increasingly trained on sensitive user data, understanding the fundamental cost of privacy in language learning becomes essential. We initiate the study of differentially private (DP) language identification and generation in the agnostic statistical setting, establishing algorithms and matching lower bounds that precisely quantify the cost of privacy. For both tasks, approximate (𝜀, 𝛿)-DP with constant 𝜀 > 0 recovers the non-private error rates: exp(−𝑟 (𝑛)) for identification (for any 𝑟 (𝑛) = 𝑜 (𝑛)) and exp(−Ω(𝑛)) for generation. Under pure 𝜀-DP, the exponents degrade by a multiplicative factor of min{1, 𝜀}, which we show is tight up to constants. Notably, for generation under pure DP with mild assumptions, the upper bound exp(− min{1, 𝜀} · Ω(𝑛)) matches the lower bound up to some constants, establishing an optimal rate. Our results show that the cost of privacy in language learning is surprisingly mild: absent entirely under approximate DP, and exactly a min{1, 𝜀} factor in the exponent under pure DP.

Introduction

Differential privacy [Dwork et al., 2006b] provides a mathematically rigorous framework for learning from sensitive data, yet its cost is not uniform across tasks: some learning problems can be solved privately at no statistical penalty, while others suffer an unavoidable degradation. Understanding the price of privacy for a specific learning problem is a central question in private learning theory. Language identification and generation, as fundamental tasks in language learning, are a natural setting in which to ask this question, especially given the growing practice of training LLMs on sensitive data, where differentially private fine-tuning has already shown strong empirical performance, sometimes approaching non-private baselines [Li et al., 2022; Yu et al., 2022], and the compute-privacy-utility tradeoff of private training is empirically characterized [McKenna et al., 2025]. Yet despite this practical progress, the fundamental theoretical cost of privacy for these tasks remains largely unexplored. we address this gap by establishing a complete characterization of the price of privacy for both language identification and generation. The formal study of language learnability traces back to the seminal work of Gold [1967], who introduced the identification in the limit model, and to Angluin [1980a,b], who characterized identifiability for several important language classes. These classical results revealed fundamental barriers: for instance, even the class of all regular languages is not identifiable in the limit from positive examples alone. Recently, Kleinberg and Mullainathan [2024] proposed generation as an alternative objective: rather than naming the target language, the learner need only produce a novel string consistent with the underlying distribution. ∗ [email protected] † [email protected] ‡ [email protected] § [email protected]

This relaxation turns out to be dramatically more powerful: generation is achievable for every countable language collection, sidestepping the classical impossibility results for identification. The aforementioned results all operate in an online setting, where the learner receives examples one at a time from an adversarially chosen sequence and must eventually converge to a correct hypothesis. Kalavasis et al. [2025] initiated the study of language learning in the statistical setting, where the learner receives an i.i.d. sample of fixed size drawn from some unknown distribution, and Høgsgaard and Pabbaraju [2026] extended this framework to the agnostic case, where the target distribution need not be supported on any single language in the collection. Our setup follows the agnostic statistical language learning model introduced by Høgsgaard and Pabbaraju [2026]. A learner receives 𝑛 i.i.d. samples 𝑆 = (𝑥 1, . . . , 𝑥𝑛 ) ∼ D 𝑛 drawn from an unknown distribution D over a countable universe U, together with a countable collection C = {𝐿1, 𝐿2, . . .} of languages, where each language 𝐿𝑖 is a subset of U. This setting gives rise to two fundamental tasks: • Language Identification: Output a language b 𝐿] is close to 𝐿 ∈ C whose population risk Pr𝑥∼D [𝑥 ∉ b the best achievable within C. • Language Generation: Output a string 𝑥b ∈ U that is both valid (b 𝑥 ∈ supp(𝐷)) and novel (b 𝑥 ∉ 𝑆) with high probability. Without privacy constraints, Høgsgaard and Pabbaraju [2026] showed that identification error decays at a nearly exponential rate exp(−𝑟 (𝑛)) where 𝑟 is any sublinear function (i.e., 𝑟 (𝑛) = 𝑜 (𝑛)) under an attainability condition on the agnostic optimum, and that generation error decays at a fully exponential rate exp(−Ω(𝑛)) under mild structural assumptions. This raises a natural question: What is the price of differential privacy for language identification and generation?

1.1

Main Results

Our answer is optimistic and we show: under approximate (𝜀, 𝛿)-DP with constant 𝜀 > 0, privacy is free; under pure 𝜀-DP, the convergence exponent degrades by exactly a multiplicative factor of min{1, 𝜀}, and this scaling is tight. Table 1 gives the complete picture. Table 1: Summary of error rates for language identification and generation. Approximate DP assumes 𝜀 = Ω(1) and 𝛿 ≥ exp(− poly(𝑛)). Generation rates under pure DP assume a known mass floor; see Section 4. ★Holds for every 𝑟 (𝑛) = 𝑜 (𝑛); the algorithm may depend on 𝑟 . † Non-private results are due to Høgsgaard and Pabbaraju [2026]. ‡ The non-private lower bound applies to any approximate DP algorithm.

Identification (UB)★ Identification (LB) ‡ Generation (UB) Generation (LB) ‡

Non-private† exp −𝑟 (𝑛) exp −𝑂 (𝑛) exp −Ω(𝑛) exp −𝑂 (𝑛)

Pure 𝜀-DP exp − min{1, 𝜀} · 𝑟 (𝑛)

exp − min{1, 𝜀} · 𝑂 (𝑛)

exp − min{1, 𝜀} · Ω(𝑛)

exp − min{1, 𝜀} · 𝑂 (𝑛)

Approx. (𝜀, 𝛿)-DP exp −𝑟 (𝑛) exp −𝑂 (𝑛) exp −Ω(𝑛) exp −𝑂 (𝑛)

Two key takeaways stand out. First, approximate DP eliminates the privacy cost entirely for both tasks, yielding a qualitative separation from pure DP. Second, generation enjoys a tighter privacy-utility tradeoff than identification: the pure DP upper and lower bounds match up to constants in the exponent, whereas identification retains an 𝑜 (𝑛) vs. 𝑂 (𝑛) gap inherited from the non-private setting. We establish these rates 2

through three contributions, each addressing a distinct technical challenge in privatizing the non-private algorithms of Høgsgaard and Pabbaraju [2026]. We summarize the key ideas and techniques below. • DP Identification (Section 3). The non-private algorithm employs a margin-based selection rule that is discontinuous: changing a single sample can flip which indices satisfy the margin constraint. We replace it with a smooth score function that jointly encodes the preference for large language indices and the penalty for failing the margin test, and privatize it via the exponential mechanism (pure DP) and the Gaussian mechanism (approximate DP). The score has sensitivity Θ(𝑓 (𝑛) 2 /𝑛), where 𝑓 is an increasing function, yet the score gap on good events is Ω(1). The function 𝑓 must be carefully chosen to balance the resulting bias–variance–privacy tradeoff, which yields the rates in Table 1. • DP Generation (Section 4). The non-private pointer-based rule has unbounded sensitivity: a single sample change can cause a language’s pointer to jump arbitrarily. We replace it with a thresholded prefix count, defined as the minimum number of times each relevant string appears in the sample, whose sensitivity is a constant, independent of 𝑛 and 𝑓 (𝑛). We again privatize via the exponential mechanism (pure DP) and the Gaussian mechanism (approximate DP). This structural advantage is the key reason generation achieves strictly better rates: the score gap grows as Ω(𝑛) while the sensitivity stays 𝑂 (1), yielding a fully exponential rate exp(− min{1, 𝜀} · Ω(𝑛)) under pure DP. We present the algorithm first with a public witness bound for clarity, then extend it to the setting where no such bound is available. • Lower Bounds (Section 5). We prove that the min{1, 𝜀} scaling in the exponent is tight for both tasks. For each task, we construct a pair of hard distributions that are close in Hamming distance under a natural coupling, then apply group privacy to show that any 𝜀-DP algorithm must incur error at least exp(− min{1, 𝜀} · 𝑂 (𝑛)). The two arguments differ in structure. For identification, the construction is symmetric: the two distributions swap the roles of two languages, and the coupling lemma constrains the misidentification probability in both directions simultaneously. For generation, the construction is inherently asymmetric: the two distributions share a common high-probability element but have disjoint “private” supports, so that any string witnessing success under one distribution necessarily witnesses failure under the other. The coupling lemma then forces any 𝜀-DP algorithm to fail on at least one distribution. For generation, the resulting lower bound matches the upper bound up to constants in the exponent, establishing an optimal rate of exp(−Θ(min{1, 𝜀} · 𝑛)). Broader perspective. Our results reveal that the price of privacy in language learning is governed by the sensitivity structure of the learning objective, not just the complexity of the hypothesis class. Concretely, generation exploits a score with constant sensitivity and achieves non-private rates under both pure and approximate DP, whereas identification relies on a margin criterion whose sensitivity grows with the horizon and consequently pays a larger cost under pure DP. This contrast supplies concrete evidence for a broader design principle: reformulating a learning objective to reduce its sensitivity structure can reduce the privacy-utility tradeoff. While our information-theoretic framework does not directly model the DP-SGD pipeline for large language models [Abadi et al., 2016; Li et al., 2022; Ponomareva et al., 2025], we hope this principle may nonetheless offer guidance for practical algorithm design.

1.2

Related Work

Language Identification and Generation. The formal study of language learnability was initiated by Gold [1967] and characterized by Angluin [1980a,b]. Kleinberg and Mullainathan [2024] introduced the weaker notion of generation in the limit, sparking a rich line of follow-up work on diversity–hallucination tradeoffs, noise robustness, and computational barriers [Kalavasis et al., 2025, 2026; Charikar and Pabbaraju,

2025; Kleinberg and Wei, 2025b,a; Raman and Raman, 2025; Bai et al., 2026; Mehrotra et al., 2025; Arenas et al., 2025]. Kalavasis et al. [2025] and Høgsgaard and Pabbaraju [2026] transitioned the problem to the statistical setting: the former under realizability, the latter in the agnostic case that we adopt. We defer the more comprehensive review to the Appendix. Private Hypothesis Selection and PAC Learning. Our identification algorithms can be viewed as private model selection over a countably infinite class with a growing horizon 𝑓 (𝑛) → ∞, extending the finite-class setting of Bun et al. [2015] and Gopi et al. [2020] and introducing a bias-variance-privacy tradeoff whose sensitivity scales as Θ(𝑓 (𝑛) 2 /𝑛). Our generation algorithms exploit a score with constant sensitivity, yielding tighter rates; our lower bounds build on the coupling and group-privacy framework of Acharya et al. [2021]. A central question in private learning theory is whether privacy degrades statistical performance. Alon et al. [2019] and Bun et al. [2020] showed that approximate DP learnability is equivalent to online learnability, while pure DP imposes a strictly stronger requirement; at the level of rates, Smith [2011]; Feldman and Xiao [2015]; Bun et al. [2015] established that approximate DP often preserves non-private rates whereas pure DP can incur an arbitrarily larger sample cost. Separations of this kind have been demonstrated for private learning [Beimel et al., 2013], counting queries [Bun et al., 2014], and marginal estimation [Steinke and Ullman, 2017]. Our results contribute a new instance of this phenomenon in the language learning setting: approximate DP recovers non-private rates for both tasks, while pure DP degrades the exponent by exactly min{1, 𝜀}. Organization. Section 2 sets up the formal framework and reviews the necessary tools from differential privacy. Section 3 presents our private identification algorithms under both pure and approximate DP. Section 4 develops the private generation algorithms, first with a public witness bound and then without. Section 5 establishes matching lower bounds for both tasks. Section 6 concludes with a discussion of limitations and future directions. Additional related work and all deferred proofs appear in the Appendix.

Preliminaries

Notation. Let ℕ denote the positive integers and [𝑛] := {1, . . . , 𝑛} for an 𝑛 ∈ ℕ. For 𝑎 ∈ ℝ, we write 𝑎 + := max{𝑎, 0}. We use ∥ · ∥ 2 for the ℓ2 -norm, N (𝜇, Σ) for the multivariate Gaussian, and 1{·} for the indicator function. Given a distribution D over U, its support is supp(D) := {𝑥 ∈ U : D (𝑥) > 0}. We write 𝑥 ∼ 𝑆 to denote a uniform draw from a finite set 𝑆. Note that we also use ∼ for the neighboring relation between datasets (𝑆 ∼ 𝑆 ′ ), but the meaning should be clear from context. We use standard asymptotic notation 𝑂, Ω, Θ, 𝑜, 𝜔 and write ≲, ≳, ≍ as synonyms for 𝑂, Ω, Θ respectively.

2.1

Language Identification and Generation

Let U = {𝑢 1, 𝑢 2, . . .} be a countable universe of strings. A language is any subset 𝐿 ⊆ U, and a language collection C ⊆ 2 U is indexed as C = {𝐿1, 𝐿2, . . .} when countable. Let D be an unknown distribution over U. For any language 𝐿, its population risk is err D (𝐿) := Pr𝑥∼D [𝑥 ∉ 𝐿], and its empirical risk on a sample Í 𝑆 = (𝑥 1, . . . , 𝑥𝑛 ) is err𝑆 (𝐿) := 𝑛1 𝑛𝑡=1 1{𝑥𝑡 ∉ 𝐿}. We work in the agnostic statistical setting of Høgsgaard and Pabbaraju [2026], building on the realizable framework of Kalavasis et al. [2025]. Language Identification. An identification algorithm A id observes 𝑆 = (𝑥 1, . . . , 𝑥𝑛 ) ∼ D 𝑛 and outputs a language A id (𝑆) ∈ C. Its identification error is the expected excess risk over the agnostic optimum: IdErr(A id, D, C, 𝑛) := 𝔼𝑛 err D (A id (𝑆)) − inf err D (𝐿), 𝐿∈ C

𝑆∼D ,𝑟

where 𝑟 denotes the internal randomness of the algorithm. Language Generation. A generation algorithm A gen observes 𝑆 ∼ D 𝑛 and outputs a string A gen (𝑆) ∈ U that should be both valid (in supp(D)) and novel (not in 𝑆). Its generation error is the failure probability: GenErr(A gen, D, C, 𝑛) := Pr𝑛 A gen (𝑆) ∉ supp(D) \ 𝑆 , 𝑆∼D ,𝑟

where 𝑟 denotes the internal randomness of the algorithm. Remark 2.1. The generation error GenErr(A gen, D, C, 𝑛) seems depending only on the distribution D and sample size 𝑛, and is entirely independent of the language collection C. In particular, agnostic generation does not require the learner to first identify which language in C best fits the data, and it suffices to produce a novel string in supp(D). However, without structural assumptions relating D to C, Høgsgaard and Pabbaraju [2026] showed that the generation error can be arbitrarily bad.

2.2

Differential Privacy

Two datasets 𝑆, 𝑆 ′ ∈ U𝑛 are neighboring, written 𝑆 ∼ 𝑆 ′ , if they differ in exactly one entry. Definition 2.2 (Differential Privacy [Dwork et al., 2006b]). A randomized algorithm A : U𝑛 → R is (𝜀, 𝛿)-differentially private if for every pair of neighboring datasets 𝑆 ∼ 𝑆 ′ and every measurable F ⊆ R, Pr[A (𝑆) ∈ F ] ≤ 𝑒 𝜀 · Pr[A (𝑆 ′ ) ∈ F ] + 𝛿. When 𝛿 = 0 we say A is 𝜀-DP (pure DP); when 𝛿 > 0 we say (𝜀, 𝛿)-DP (approximate DP), typically with 𝛿 ≤ 1/poly(𝑛). Lemma 2.3 (Post-Processing [Dwork and Roth, 2014]). If A is (𝜀, 𝛿)-DP and ℎ is any (possibly randomized) function, then ℎ ◦ A is (𝜀, 𝛿)-DP. Exponential mechanism. The exponential mechanism McSherry and Talwar [2007], which is the canonical tool for privately optimizing over a discrete set: it selects outcomes with probability exponentially weighted by their scores, achieving pure DP without requiring the output space to be numeric. ′ Given a score function 𝑞 : U𝑛 × R → ℝ with sensitivity Δ𝑞 := max𝑖 ∈ R max𝑆∼𝑆 ′ |𝑞(𝑆, 𝑖) − 𝑞(𝑆 ,𝑖)|. The 𝜀 exponential mechanism EM𝜀 (𝑆, 𝑞, R) selects and outputs 𝑖 ∈ R with probability ∝ exp 2Δ𝑞 𝑞(𝑆, 𝑖) . Lemma 2.4 (McSherry and Talwar [2007]; Dwork and Roth [2014]). The exponential mechanism EM𝜀 (𝑆, 𝑞, R) is 𝜀-DP. Moreover, for any 𝛽 ∈ (0, 1), with probability ≥ 1 − 𝛽 the output satisfies 𝑞(𝑆, 𝑖) ≥ OPT𝑞 (𝑆) −

2Δ𝑞 |R| log , 𝜀 𝛽

where OPT𝑞 (𝑆) := max𝑖 ∈ R 𝑞(𝑆, 𝑖). Gaussian Mechanism. We make use of Gaussian mechanism [Dwork et al., 2006a] to design our approximate-DP algorithms. Given 𝑓 : U𝑛 → ℝ𝑑 with ℓ2 -sensitivity Δ2 := max𝑆∼𝑆 ′ ∥ 𝑓 (𝑆) − 𝑓 (𝑆 ′ ) ∥ 2 , the Gaussian mechanism releases 𝑓 (𝑆) + 𝑍 with 𝑍 ∼ N (0, 𝜎 2 𝐼𝑑 ). Lemma 2.5 (Dwork et al. [2006a]; Dwork and Roth [2014]). The Gaussian mechanism is (𝜀, 𝛿)-DP if 𝜎≥

Δ2 √︁ 2 log(1.25/𝛿). 𝜀 5

Remark 2.6. Sharper variance thresholds for the Gaussian mechanism are known e.g., via Rényi DP [Mironov, 2017], the analytic Gaussian mechanism [Balle and Wang, 2018], or 𝑓 -DP [Dong et al., 2022]. They also extend the relax the requirement of 𝜀 from (0, 1) to (0, ∞). As this is a first study of differentially private language learning, we use the classical bound above for simplicity; all our results hold a fortiori under tighter calibration.

Differentially Private Language Identification

We design differentially private identification algorithms that, given 𝑆 ∼ D 𝑛 , output a language 𝐿𝑖ˆ ∈ C whose population risk is nearly as small as the agnostic optimum. We work under the following assumption, necessary for fast convergence even without privacy [Høgsgaard and Pabbaraju, 2026]. Assumption 3.1 (Agnostic optimum is attainable). There exists an index 𝑖 ★ ∈ ℕ such that err D (𝐿𝑖★ ) = inf 𝐿∈ C err D (𝐿). Let 𝑖 ★ denote the smallest such index. Score function design. The non-private algorithm of Høgsgaard and Pabbaraju [2026] selects the largest index 𝑖 ∈ [𝑓 (𝑛)] whose empirical risk beats all predecessors by a margin of at least 2/𝑓 (𝑛), where 𝑓 (𝑛) → ∞ is a growing horizon. A natural first attempt at privatization would be to use empirical risk directly as the score in the exponential mechanism. However, the agnostic setting requires selecting the largest feasible index rather than the one with minimum risk: the horizon 𝑓 (𝑛) must grow to eventually include 𝑖 ★, and smaller indices are trivially within range but suboptimal. Moreover, the non-private margin test is discontinuous in the data: changing a single sample can flip an index from feasible to infeasible, so the test cannot be privatized directly. We resolve this by replacing the hard feasibility test with a soft score that continuously encodes both objectives. For each 𝑖 ∈ [𝑓 (𝑛)], define the empirical margin ( 1, 𝑖 = 1, 𝑀𝑆 (𝑖) := min 𝑗 ∈ [𝑖 −1] err𝑆 (𝐿 𝑗 ) − err𝑆 (𝐿𝑖 ) , 𝑖 ≥ 2, 2 the deficit 𝑑𝑆 (𝑖) := 𝑓 (𝑛) − 𝑀𝑆 (𝑖) + , and the score 𝑞(𝑆, 𝑖) := 𝑖 − 𝑓 (𝑛) 2𝑑𝑆 (𝑖). The term 𝑖 rewards larger indices, while the penalty −𝑓 (𝑛) 2𝑑𝑆 (𝑖) continuously downweights indices that fail the margin test. When 𝑑𝑆 (𝑖) = 0 (margin satisfied), the score equals 𝑖; when 𝑑𝑆 (𝑖) is large, the penalty dominates. The coefficient 𝑓 (𝑛) 2 is chosen so that any index with full deficit incurs a penalty exceeding its positional reward.

3.1

Pure DP Identification

Algorithm 1 samples 𝑖ˆ from the exponential mechanism with score 𝑞 over [𝑓 (𝑛)]. id Algorithm 1 Pure DP Identification A𝜀,𝑓

Require: A dataset 𝑆 = (𝑥 1, . . . , 𝑥𝑛 ) ∈ U 𝑛 , a privacy parameter 𝜀 > 0, a function 𝑓 , a language collection C = {𝐿1, 𝐿2, . . .} 1: for 𝑖 ∈ [𝑓 (𝑛)] do Í 2: err𝑆 (𝐿𝑖 ) ← 𝑛1 𝑛𝑡=1 1{𝑥𝑡 ∉ 𝐿𝑖 } 3: end for 4: for 𝑖 ∈ [𝑓 (𝑛)] do 5: Compute 𝑀𝑆 (𝑖), 𝑑𝑆 (𝑖), and 𝑞(𝑆, 𝑖) 6: end for 7: return 𝑖ˆ ∼ EM𝜀 (𝑆, 𝑞, [𝑓 (𝑛)])

Theorem 3.2 (Pure DP Identification). Let C be a countable language collection, D any distribution over U satisfying Assumption 3.1, 𝜀 > 0, and 𝑓 : ℕ → ℕ with 𝑓 (𝑛) → ∞. Then Algorithm 1 is 𝜀-differentially private and, for all sufficiently large 𝑛 ∈ ℕ, 𝑛 𝜀𝑛 id IdErr(A𝜀,𝑓 , D, C, 𝑛) ≤ 2𝑓 (𝑛) exp − + 𝑓 (𝑛) exp − . 8𝑓 (𝑛) 2 8𝑓 (𝑛) 2 | {z } | {z } statistical term

privacy term

When 𝜀 ≥ 1 the privacy term is dominated by the statistical term and privacy is essentially free; √︁ when 𝜀 < 1 the privacy term dominates, degrading the rate by a factor of 𝜀 in the exponent. Setting 𝑓 (𝑛) = 𝑐 log 𝑛 e yields IdErr ≲ exp − min{1, 𝜀} · 𝑛/log 𝑛 = exp − min{1, 𝜀} · Ω(𝑛) . The proof of Theorem 3.2 is in Appendix D.

3.2

Approximate DP Identification

For approximate DP, we replace the exponential mechanism with the Gaussian mechanism: in Algorithm 2, we privately release a noisy empirical error vector ( ef rr𝑆 (𝐿𝑖 ))𝑖 ∈ [ 𝑓 (𝑛) ] by adding independent Gaussian noise to each coordinate, then apply the deterministic margin-selection rule for noisy margin defined as e𝑆 (𝑖) = min ef 𝑀 rr𝑆 (𝐿 𝑗 ) − ef rr𝑆 (𝐿𝑖 ) . 𝑗 ∈ [𝑖 −1]

By post-processing, the algorithm clearly preserves differential privacy. id Algorithm 2 Approximate DP Identification A𝜀,𝛿,𝑓

Require: A dataset 𝑆 ∈ U𝑛 , privacy parameters 𝜀 > 0, 𝛿 ∈ (0, 1), a function 𝑓 : ℕ → ℕ, a language collection C 1: for 𝑖 ∈ [𝑓 (𝑛)] do Í 2: err𝑆 (𝐿𝑖 ) ← 𝑛1 𝑛𝑡=1 1{𝑥𝑡 ∉ 𝐿𝑖 } 3: end for √ 𝑓 (𝑛) √︁ 4: 𝜎 ← 𝜀𝑛 2 log(1.25/𝛿) 5: for 𝑖 ∈ [𝑓 (𝑛)] do 6: Sample 𝑍𝑖 ∼ N (0, 𝜎 2 ) 7: ef rr𝑆 (𝐿𝑖 ) ← err𝑆 (𝐿𝑖 ) + 𝑍𝑖 8: end for 9: for 𝑖 ∈ [𝑓 (𝑛)] do e𝑆 (𝑖) ← min 𝑗 ∈ [𝑖 −1] ef 10: 𝑀 rr𝑆 (𝐿 𝑗 ) − ef rr𝑆 (𝐿𝑖 ) 11: end for e𝑆 (𝑖) > 2/𝑓 (𝑛) 12: return 𝑖ˆ ← max 𝑖 ∈ [𝑓 (𝑛)] : 𝑀 √︁ The empirical error vector has ℓ2 -sensitivity 𝑓 (𝑛)/𝑛. Correctness on the event E ∩ F , where E is the concentration event from above and F is the event that all Gaussian perturbations are at most 1/(4𝑓 (𝑛)), is deterministic: the noisy errors deviate from population values by at most 1/(2𝑓 (𝑛)), ensuring 𝑖 ★ passes the noisy margin test and all 𝑖 > 𝑖 ★ fail. Theorem 3.3 (Approximate DP Identification). Under the same conditions as Theorem 3.2, let 𝜀, 𝛿 ∈ (0, 1). Then Algorithm 2 is (𝜀, 𝛿)-differentially private and, for all sufficiently large 𝑛, id IdErr(A𝜀,𝛿,𝑓 , D, C, 𝑛) ≤ 2𝑓 (𝑛) exp −

𝑛 𝜀 2𝑛 2 + 2𝑓 (𝑛) exp − . 8𝑓 (𝑛) 2 64𝑓 (𝑛) 3 log(1.25/𝛿) 7

√︁ Setting 𝑓 (𝑛) = 𝑐 log 𝑛 yields IdErr ≲ exp(−𝑛/log 𝑛) for any 𝜀 = Ω(1) and 𝛿 ≥ exp(− poly(𝑛)), matching the non-private rate of Høgsgaard and Pabbaraju [2026]. Hence, under approximate DP with constant privacy parameters, identification incurs no asymptotic cost relative to its non-private counterpart. When 𝜀 → 0, the two mechanisms diverge: the pure DP rate degrades as exp(−𝜀 · 𝑟 (𝑛)) for any 𝑟 (𝑛) = 𝑜 (𝑛) while the approximate DP rate degrades as exp(−𝜀 2 · 𝑟 (𝑛)), making pure DP preferable in the low-privacy regime 𝜀 ≪ 1. The proof of Theorem 3.3 is in Appendix D.

Differentially Private Language Generation

We design differentially private generation algorithms that, given 𝑆 ∼ D 𝑛 , output a novel string from supp(D) \ 𝑆. We fix an enumeration U = {𝑢𝑖 }𝑖 ∈ℕ and assume every language 𝐿 ∈ C is infinite. Definition 4.1 (Witness Index). The witness index is defined as 𝑖 (C, D) := inf {𝑖 ∈ ℕ : ∀ 𝐿 ∈ C with 𝐿 ⊈ supp(D), ∃ 𝑘 ≤ 𝑖 s.t. 𝑢𝑘 ∈ 𝐿 \ supp(D)}, with the convention inf ∅ = ∞. In words, 𝑖 (C, D) is the smallest prefix length such that every language not fully contained in supp(D) has a witness (a string in the language but outside the support) within the first 𝑖 (C, D) elements of U. We work under the following assumptions [Høgsgaard and Pabbaraju, 2026]. Assumption 4.2 (Finite witness index). The witness index is finite, i.e., 𝑖 (C, D) < ∞. Assumption 4.3 (Support contains a reference language). There exists 𝑖 ★ ∈ ℕ such that 𝐿𝑖★ ⊆ supp(D). Let 𝑖 ★ denote the smallest such index. Both assumptions are necessary for generation and are inherited from the non-private setting. Assumption 4.2 ensures that every language not contained in supp(D) can be ruled out by a finite prefix of the enumeration: without it, no finite sample could distinguish good languages from bad ones. Assumption 4.3 guarantees that at least one language in C is fully supported by D, so that a valid novel string exists; without it, every language would contain strings outside supp(D), making correct generation impossible. Score function design. The non-private algorithm in [Høgsgaard and Pabbaraju, 2026] maintains, for each language 𝐿𝑖 , a pointer: the index of the smallest string in 𝐿𝑖 ∩ {𝑢 1, . . . , 𝑢𝑊 } not yet seen in the sample. For good languages (𝐿𝑖 ⊆ supp(D)), all prefix strings eventually appear in the sample and the pointer advances past the witness window; for bad languages (𝐿𝑖 ⊈ supp(D)), the pointer gets stuck at their witness. However, this pointer has unbounded sensitivity. We replace the pointer with a thresholded prefix count. For each language 𝐿𝑖 and a witness window [𝑊 ], let 𝐼𝑖 (𝑊 ) := {𝑘 ∈ [𝑊 ] : 𝑢𝑘 ∈ 𝐿𝑖 } and define the minimum prefix count ( min𝑘 ∈𝐼𝑖 (𝑊 ) 𝑁𝑆 (𝑢𝑘 ), if 𝐼𝑖 (𝑊 ) ≠ ∅, 𝑊 𝑎𝑖 (𝑆) := 𝑛, if 𝐼𝑖 (𝑊 ) = ∅, Í where 𝑁𝑆 (𝑢𝑘 ) := 𝑛𝑡=1 1{𝑥𝑡 = 𝑢𝑘 }. Rather than asking whether every relevant prefix string has appeared at least once, we ask whether these strings have appeared at least 𝑔(𝑛) times for a threshold 𝑔(𝑛) → ∞. The 𝑊 𝑊 deficit is 𝑑𝑖𝑊 (𝑆) := (𝑔(𝑛) − 𝑎𝑊 𝑖 (𝑆))+ and the score is 𝑞 (𝑆, 𝑖) := −𝑑𝑖 (𝑆). The score is 0 when the prefix is well-covered (good language) and −𝑔(𝑛) when a witness string is never observed (bad language).

Remark 4.4 (Constant Sensitivity). The generation score has sensitivity Δ = 1 since each multiplicity 𝑁𝑆 (𝑢𝑘 ) changes by at most 1 under a neighboring dataset, the minimum preserves Lipschitz constants, and (𝑔(𝑛) − ·)+ is 1-Lipschitz. This is in sharp contrast with the identification score (Section 3), whose sensitivity scales as Θ(𝑓 (𝑛) 2 /𝑛). The constant sensitivity is the structural reason generation achieves a tighter privacy–utility tradeoff: the score gap grows as Ω(𝑛) while the sensitivity stays 𝑂 (1), giving the exponential mechanism far more room.

4.1

Pure DP Generation with a Public Witness Bound

We first consider the setting where a public upper bound 𝑊 ≥ 𝑖 (C, D) is available (given to the algorithm before observing 𝑆 and therefore not protected by DP). gen

Algorithm 3 Pure DP Generation with Public Witness Bound A𝜀,𝑓 ,𝑔,𝑊 Require: A dataset 𝑆 = (𝑥 1, . . . , 𝑥𝑛 ) ∈ U𝑛 , a privacy parameter 𝜀 > 0, a public witness bound 𝑊 , functions 𝑓 , 𝑔 : ℕ → ℕ, a language collection C = {𝐿1, 𝐿2, . . .} Ensure: A string 𝑥b ∈ U 1: for 𝑘 ∈ [𝑊 ] do Í 2: 𝑁𝑆 (𝑢𝑘 ) ← 𝑛𝑡=1 1{𝑥𝑡 = 𝑢𝑘 } 3: end for 4: for 𝑖 ∈ [𝑓 (𝑛)] do 𝑊 𝑊 5: Compute 𝐼𝑖 (𝑊 ), 𝑎𝑊 𝑖 (𝑆), 𝑑𝑖 (𝑆), and 𝑞 (𝑆, 𝑖) 6: end for 7: Sample b 𝑖 ∼ EM𝜀 (𝑆, 𝑞𝑊 , [𝑓 (𝑛)]) ⊲ Privately select a language 𝑛 b 8: Sample 𝑗 ∼ Unif ( [2 ]) ⊲ Public randomness 9: return the b 𝑗 -th smallest-indexed string in 𝐿b𝑖 ∩ {𝑢𝑊 +1, 𝑢𝑊 +2, . . .} Having selected a language 𝐿b𝑖 , the algorithm outputs a uniformly random string from the first 2𝑛 elements of 𝐿b𝑖 beyond the witness window. Since 𝐿b𝑖 is infinite and (when correctly selected) contained in supp(D), these are all valid strings; the probability of colliding with a sample point is at most 𝑛/2𝑛 ≤ exp(−𝑛/2) for sufficiently large 𝑛. Theorem 4.5 (Pure DP Generation with Public Bound). Let C be a countable collection of infinite languages, ★ := {𝑘 ∈ [𝑊 ] : 𝑢 ∈ 𝐿 ★ } D any distribution over U. Suppose that Assumptions 4.2 and 4.3 hold. Define 𝐼𝑊 𝑖 𝑘 ★ and 𝑝𝑊 := min𝑘 ∈𝐼𝑊★ Pr𝑥∼D [𝑥 = 𝑢𝑘 ]. Let 𝜀 > 0 and let 𝑓 , 𝑔 : ℕ → ℕ satisfy 𝑓 (𝑛) → ∞, 𝑔(𝑛) → ∞, 𝑓 (𝑛) ≥ 𝑖 ★, ★ /2 for all large 𝑛. Then Algorithm 3 is 𝜀-differentially private and, for all sufficiently large 𝑛, and 𝑔(𝑛) ≤ 𝑛𝑝𝑊 𝜀 𝑔(𝑛) 𝑛 𝑛𝑝 ★ gen ★ GenErr(A𝜀,𝑓 ,𝑔,𝑊 , D, C, 𝑛) ≤ |𝐼𝑊 | exp − 𝑊 + 𝑓 (𝑛) exp − + exp − . 8 4 2 {z } | {z } | {z } | coverage

private selection

collision

★ is known, setting 𝑔(𝑛) = ⌊𝑛𝑝 /2⌋ yields GenErr ≲ exp(− min{1, 𝜀}·𝑛), If a constant lower bound 𝑝 0 ≤ 𝑝𝑊 0 matching the lower bound of Theorem 5.6 up to constants in the exponent. The proof is in Appendix E.

4.2

Pure DP Generation without a Public Witness Bound

When no public bound on 𝑖 (C, D) is available, we jointly search over both the language index 𝑖 and a candidate witness threshold 𝑡. For each pair (𝑖, 𝑡) ∈ [𝑓 (𝑛)] × [ℎ(𝑛)], define the prefix count 𝑎𝑖,𝑡 (𝑆) and

deficit 𝑑𝑖,𝑡 (𝑆) analogously to the public-bound case with 𝑡 replacing 𝑊 , and the pair score 𝑞 pair (𝑆, (𝑖, 𝑡)) := 𝑡 −

ℎ(𝑛) 𝑑𝑖,𝑡 (𝑆). 𝑔(𝑛)

(4.1)

The term 𝑡 rewards larger thresholds (indicating progress past the witness window), while the penalty ℎ (𝑛) 𝑔 (𝑛) 𝑑𝑖,𝑡 (𝑆) suppresses languages that fail the witness test at threshold 𝑡. The coefficient ℎ(𝑛)/𝑔(𝑛) is chosen so that a bad language with full deficit 𝑔(𝑛) incurs a penalty of exactly ℎ(𝑛), ensuring its score is at most 𝑡 − ℎ(𝑛) ≤ 0. The algorithm applies the exponential mechanism over the product range [𝑓 (𝑛)] × [ℎ(𝑛)] and outputs a string from the selected language beyond the selected threshold (see Algorithm 6 in the Appendix). Sensitivity and score gap. The pair score has sensitivity ℎ(𝑛)/𝑔(𝑛), higher than the constant sensitivity of the public-bound case; this is the cost of not knowing the witness bound. However, the score gap also grows: on the coverage event, the good pair (𝑖 ★, ℎ(𝑛)) achieves score ℎ(𝑛) while every bad pair achieves score at most 𝑖 (C, D) − 1 ≤ ℎ(𝑛)/2 − 1 (when ℎ(𝑛) ≥ 2 𝑖 (C, D)). The effective ratio gap/sensitivity is thus approximately 𝑔(𝑛), comparable to the public-bound case. Theorem 4.6 (Pure DP Generation without Public Bound). Let C be a countable collection of infinite languages, D any distribution over U, and suppose Assumptions 4.2 and 4.3 hold. Let 𝜀 > 0 and let 𝑓 , 𝑔, ℎ : ℕ → ℕ satisfy 𝑓 (𝑛) ≥ 𝑖 ★, ℎ(𝑛) ≥ 2 𝑖 (C, D), 𝑔(𝑛) → ∞, and 𝑔(𝑛) ≤ 𝑛𝑝ℎ★/2 for all large 𝑛, where 𝑝ℎ★ := min𝑘 ∈𝐼ℎ★ Pr𝑥∼D [𝑥 = 𝑢𝑘 ] and 𝐼ℎ★ := {𝑘 ∈ [ℎ(𝑛)] : 𝑢𝑘 ∈ 𝐿𝑖★ }. Then there exists an algorithm (Algorithm 6) that is 𝜀-differentially private and, for all sufficiently large 𝑛, 𝑛𝑝 ★ 𝜀 𝑔(𝑛) 𝑛 gen ★ GenErr(A𝜀,𝑓 ,𝑔,ℎ , D, C, 𝑛) ≤ |𝐼ℎ | exp − ℎ + 𝑓 (𝑛) ℎ(𝑛) exp − + exp − . 8 8 2 The bound has the similar structure as Theorem 4.5. The main difference is the enlarged prefactor 𝑓 (𝑛) ℎ(𝑛) in the privacy term (reflecting the larger search space [𝑓 (𝑛)] × [ℎ(𝑛)]). The proof is in Appendix E. Corollary 4.7 (Exponential rate with known mass floor). Under the conditions of Theorem 4.6, if a constant lower bound 𝑝 0 ≤ 𝑝ℎ★ is known, setting 𝑔(𝑛) = ⌊𝑛𝑝 0 /2⌋ and choosing 𝑓 , ℎ with log(𝑓 (𝑛) ℎ(𝑛)) = 𝑜 (𝑛) yields GenErr ≲ exp − min{1, 𝜀} · 𝑛 . Corollary 4.8 (Subexponential rate without known mass floor). Without a known mass floor, for any 𝑟 (𝑛) → ∞ with 𝑟 (𝑛) = 𝑜 (𝑛), setting 𝑔(𝑛) = ⌊𝑟 (𝑛)⌋ and choosing 𝑓 , ℎ with log(𝑓 (𝑛) ℎ(𝑛)) = 𝑜 (𝑟 (𝑛)) yields GenErr ≲ exp −𝜀 · 𝑟 (𝑛) .

4.3

Approximate DP Generation

For approximate DP, we replace the exponential mechanism with the Gaussian mechanism: independent Gaussian noise is added to each pair score before taking the argmax (see Algorithm 7 in Appendix E for the full algorithm). Since the generation score has constant per-coordinate sensitivity, the ℓ2 -sensitivity of the score √︁ (𝑛) vector over [𝑓 (𝑛)] × [ℎ(𝑛)] is only ℎ𝑔 (𝑛) 𝑓 (𝑛)ℎ(𝑛), requiring Gaussian noise of standard deviation 𝜎 = √ 𝑓 (𝑛)ℎ (𝑛) √︁ ℎ (𝑛) · 2 log(1.25/𝛿). The score gap is Ω(ℎ(𝑛)) and grows linearly with ℎ(𝑛), while 𝜎 grows only 𝑔 (𝑛) 𝜀 √︁ 3/2 as ℎ(𝑛) 𝑓 (𝑛) / (𝜀 𝑔(𝑛)). When 𝑔(𝑛) ≍ 𝑛 (known mass floor) and 𝑓 (𝑛), ℎ(𝑛) grow slowly, the noise is negligible relative to the gap, eliminating the privacy cost entirely. Theorem 4.9 (Approximate DP Generation). Under the same conditions as Theorem 4.6, there exists an algorithm (Algorithm 7) that is (𝜀, 𝛿)-differentially private and achieves GenErr ≤ exp(−Ω(𝑛)) for any constant 𝜀 > 0 and 𝛿 ≥ exp(− poly(𝑛)), matching the non-private rate. 10

Thus privacy is essentially free under approximate DP for generation. This is qualitatively different from the identification setting (Section 3.2), where approximate DP also recovers the non-private rate but e that rate is only exp(−Ω(𝑛)) rather than exp(−Ω(𝑛)). The fundamental reason is the constant sensitivity √︁ of the generation score: the Gaussian noise magnitude 𝜎 ∝ 𝑓 (𝑛)/𝜀 is negligible relative to the score gap 𝑔(𝑛) ∝ 𝑛, so the noise concentration event holds with probability 1 − exp(−𝜔 (𝑛)). The proof of Theorem 4.9 is in Appendix E.

Lower Bounds

We show that the min{1, 𝜀} scaling in the exponent is tight for both tasks. The shared strategy is to construct a pair of hard distributions close in Hamming distance under a natural coupling, then apply group privacy to constrain any 𝜀-DP algorithm. We first state the main tool underlying both proofs. Lemma 5.1 (Group Privacy Dwork and Roth [2014]). Let A : U𝑛 → R be 𝜀-differentially private. If 𝑆, 𝑆 ′ ∈ U𝑛 differ in at most 𝑘 entries, then for every measurable F ⊆ R, we have Pr[A (𝑆) ∈ F ] ≤ exp(𝜀𝑘) Pr[A (𝑆 ′ ) ∈ F ], where the probability is taken over the randomness of A. Group privacy extends the basic DP guarantee from a single entry change to 𝑘 simultaneous changes, at the cost of multiplying the privacy parameter by 𝑘. This amplification is the key mechanism through which our lower bounds arise: if two distributions can be coupled so that their samples typically differ in 𝐾 positions, then any 𝜀-DP algorithm can only distinguish them up to a factor of exp(𝜀𝐾). A coupling between distributions D1 and D2 is a joint distribution whose marginals are D1 and D2 , respectively. The Hamming distance between two sequences 𝑆 = (𝑋 1, . . . , 𝑋𝑛 ) and 𝑆 ′ = (𝑌1, . . . , 𝑌𝑛 ) is Í defined as dHam (𝑆, 𝑆 ′ ) := 𝑛𝑡=1 1{𝑋𝑖 ≠ 𝑌𝑖 }, i.e., the number of positions where the two sequences differ. Combining group privacy with a probabilistic bound on the Hamming distance under a coupling yields the following lemma, which is the main tool for both of our lower bounds. We defer the proof to Appendix B. Lemma 5.2 (Coupling Lemma via Group Privacy, a Variant of Lemma 19 in Acharya et al. [2021]). Let A : U𝑛 → R be 𝜀-differentially private. Let (𝑆, 𝑆 ′ ) be a coupling of two distributions over U𝑛 such that Pr[dHam (𝑆, 𝑆 ′ ) > 𝐾] ≤ 𝜂 for some 𝐾 ≥ 0 and 𝜂 ∈ [0, 1]. Then for every measurable set F ⊆ R, we have Pr [A (𝑆) ∈ F ] ≤ exp(𝜀𝐾) Pr [A (𝑆 ′ ) ∈ F ] + 𝜂. ′

𝑆,𝑟

5.1

𝑆 ,𝑟

Lower Bound for DP Identification

Definition 5.3 (IPP Condition). A collection C satisfies the Intersecting Private-Pair (IPP) condition if there exist two languages 𝐿, 𝐿 ′ ∈ C with 𝐿 ∩ 𝐿 ′ ≠ ∅, such that both 𝐿 and 𝐿 ′ each contain at least one element not belonging to any other language in C. We call such element a private element to that language. Theorem 5.4 (Lower Bound for DP Identification). Let C satisfy the IPP condition. For any 𝜀-DP identification algorithm A, there exists a distribution D such that IdErr(A, D, C, 𝑛) ≳ exp(− min{1, 𝜀} · 𝑛) along infinitely many 𝑛. Proof sketch. For 𝜀 < 1, let 𝑠 0 ∈ 𝐿 ∩ 𝐿 ′ , 𝑠 1 private to 𝐿, 𝑠 2 private to 𝐿 ′ . Define D (resp. D ′ ) placing mass 3/4 on 𝑠 0 and 1/4 on 𝑠 1 (resp. 𝑠 2 ). Coupling coordinate-wise, the Hamming distance satisfies Pr[𝐻 > 𝑛/2] ≤ exp(−𝑛/12). Lemma 5.2 with 𝐾 = 𝑛/2 gives max{Pr[A (𝑆) ≠ 𝐿], Pr[A (𝑆 ′ ) ≠ 𝐿 ′ ]} ≳ exp(−𝜀𝑛/2); each misidentification costs excess risk ≥ 1/4. For 𝜀 ≥ 1, the non-private lower bound of Høgsgaard and Pabbaraju [2026] gives IdErr ≳ exp(−𝑛). Combining yields the min{1, 𝜀}. The full proof is in Appendix F. □ 11

5.2

Lower Bound for DP Generation

Definition 5.5 (IIDP Condition). A collection C satisfies the Intersecting Infinite-Difference Pair (IIDP) condition if there exist two distinct languages 𝐿, 𝐿 ′ ∈ C, an element 𝑠 0 ∈ 𝐿 ∩ 𝐿 ′ , and two infinite sequences of distinct elements (𝑎𝑘 )𝑘 ≥1 ⊆ 𝐿 \ 𝐿 ′ and (𝑏𝑘 )𝑘 ≥1 ⊆ 𝐿 ′ \ 𝐿. The IIDP condition strengthens IPP by requiring infinitely many private elements on each side, which is necessary because the hard distributions for generation must have infinite support. Theorem 5.6 (Lower Bound for DP Generation). Let C satisfy the IIDP condition and the condition of Theorem 3.4 in Høgsgaard and Pabbaraju [2026] (i.e., there exist 𝐿, 𝐿 ′ ∈ C with |𝐿 ∩ 𝐿 ′ | < ∞ and U \ (𝐿 ∪ 𝐿 ′ ) ≠ ∅). For any 𝜀-DP generation algorithm A, there exists a distribution D such that GenErr(A, D, C, 𝑛) ≳ exp(− min{1, 𝜀} · 𝑛) along infinitely many 𝑛. Proof sketch. The argument is asymmetric, unlike the symmetric identification proof. Let (𝑎𝑘 ) ⊆ 𝐿 \ 𝐿 ′ , (𝑏𝑘 ) ⊆ 𝐿 ′ \ 𝐿 witness IIDP with 𝑠 0 ∈ 𝐿 ∩ 𝐿 ′ . Define D by Pr[𝑥 = 𝑠 0 ] = 3/4, Pr[𝑥 = 𝑎𝑘 ] = 2−𝑘 /4, and D ′ analogously with 𝑏𝑘 . Let 𝐹 := {𝑎𝑘 : 𝑘 ≥ 1}. The set 𝐹 plays opposite roles: • Under D: 𝑠 0 ∈ 𝑆 w.h.p., so success requires A (𝑆) ∈ 𝐹 ; hence Pr[A (𝑆) ∈ 𝐹 ] ≥ 1 − 𝛼 − 4−𝑛 . • Under D ′ : 𝐹 ∩ supp(D ′ ) = ∅, so A (𝑆 ′ ) ∈ 𝐹 implies failure; hence Pr[A (𝑆 ′ ) ∈ 𝐹 ] ≤ 𝛼 ′ . Lemma 5.2 gives Pr[A (𝑆) ∈ 𝐹 ] ≤ 𝑒 𝜀𝑛/2 · Pr[A (𝑆 ′ ) ∈ 𝐹 ] + 𝑒 −𝑛/12 . Hence 1 − 𝛼 − 4−𝑛 ≤ 𝑒 𝜀𝑛/2𝛼 ′ + 𝑒 −𝑛/12 , which rearranges to max{𝛼, 𝛼 ′ } ≳ exp(−𝜀𝑛/2). Combining with the non-private bound of Høgsgaard and Pabbaraju [2026] for 𝜀 ≥ 1 gives the result. The full proof is in Appendix F. □ Remark 5.7 (Concrete Instance Satisfying the Conditions of Theorems 5.4 and 5.6). Let U = ℕ, 𝐿 = {1} ∪ {3𝑘 : 𝑘 ≥ 1}, and 𝐿 ′ = {1} ∪ {3𝑘 + 1 : 𝑘 ≥ 1}. Then 𝐿 ∩ 𝐿 ′ = {1} is finite, 𝑎𝑘 = 3𝑘 ∈ 𝐿 \ 𝐿 ′ and 𝑏𝑘 = 3𝑘 + 1 ∈ 𝐿 ′ \ 𝐿 witness the IIDP condition, and 2 ∈ U \ (𝐿 ∪ 𝐿 ′ ). Hence any collection C ⊇ {𝐿, 𝐿 ′ } satisfies all conditions needed for both lower bounds.

Conclusion and Future Work

We initiated the study of differentially private language identification and generation in the agnostic statistical setting, establishing algorithms and matching lower bounds that precisely quantify the cost of privacy. For both tasks, approximate (𝜀, 𝛿)-DP with constant 𝜀 > 0 recovers the non-private error rates of Høgsgaard and Pabbaraju [2026], while pure 𝜀-DP degrades the convergence exponent by a multiplicative factor of min{1, 𝜀}, which our lower bounds confirm is tight. Our results are information-theoretic: we characterize nearly optimal error rates but do not address computational efficiency, and our algorithms require explicit enumeration of languages and universe elements. Bridging these guarantees with the empirical DP-SGD pipeline for LLM training [Abadi et al., 2016; Li et al., 2022; Ponomareva et al., 2023, 2025] remains an important challenge. Recent work on computational barriers for (non-private) language generation [Arenas et al., 2025] suggests that efficient algorithms may need more structural assumptions. Future directions include studying DP language learning in the online setting of Gold [1967] and Kleinberg and Mullainathan [2024], where adversarial samples and infinite-horizon composition require fundamentally different privacy analyses, and exploring user-level privacy [Liu et al., 2020; Levy et al., 2021; Ghazi et al., 2023], where the protected unit is an entire sequence of strings from a single user. Finally, extending our results to richer generation objectives that incorporate safety constraints [Anastasopoulos et al., 2026] or representativeness requirements [Peale et al., 2025] while maintaining differential privacy is a natural next step. 12

References Martín Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 308–318, 2016. Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private Assouad, Fano, and Le Cam. In Algorithmic Learning Theory (ALT), pages 48–78. PMLR, 2021. Ishaq Aden-Ali, Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded high-dimensional Gaussians. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT), pages 185–216. PMLR, 2021. Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite Littlestone dimension. In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), pages 852–860, 2019. Antonios Anastasopoulos, Giuseppe Ateniese, and Evgenios M Kornaropoulos. Safe language generation in the limit. arXiv preprint arXiv:2601.08648, 2026. Dana Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21(1): 46–62, August 1980a. ISSN 0022-0000. doi: 10.1016/0022-0000(80)90041-0. Dana Angluin. Inductive inference of formal languages from positive data. Information and Control, 45(2): 117–135, 1980b. Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, and Pasin Manurangsi. Large-scale differentially private BERT. In Findings of the Association for Computational Linguistics: EMNLP 2022, pages 6481–6491. Association for Computational Linguistics, 2022. doi: 10.18653/v1/2022.findings-emnlp.484. Marcelo Arenas, Pablo Barceló, Luis Cofré, and Alexander Kozachinskiy. Language generation: Complexity barriers and implications for learning. arXiv preprint arXiv:2511.05759, 2025. 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). SIAM, 2026. doi: 10.1137/1.9781611978971.31. Borja Balle and Yu-Xiang Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 394–403. PMLR, 2018. Amos Beimel, Kobbi Nissim, and Uri Stemmer. Private learning and sanitization: Pure vs. approximate differential privacy. In Approximation, Randomization, and Combinatorial Optimization (APPROX/RANDOM), volume 8096 of Lecture Notes in Computer Science, pages 363–378. Springer, 2013. Alex Bie, Gautam Kamath, and Vikrant Singhal. Private estimation with public data. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 18653–18666, 2022. Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 02 2013. ISBN 9780199535255. Mark Bun. A computational separation between private learning and online learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2020. 13

Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 1–10. ACM, 2014. Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In Proceedings of the 56th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 634–649, 2015. Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 389–402, 2020. Moses Charikar and Chirag Pabbaraju. Exploring facets of language generation in the limit. In Proceedings of the Thirty-Eighth Conference on Learning Theory (COLT), volume 291 of Proceedings of Machine Learning Research, pages 854–887. PMLR, 2025. Moses Charikar and Chirag Pabbaraju. Pareto-optimal non-uniform language generation. In Proceedings of the International Conference on Algorithmic Learning Theory (ALT), 2026. Moses Charikar, Chirag Pabbaraju, and Ambuj Tewari. A characterization of list language identification in the limit. arXiv preprint arXiv:2511.04103, 2025. Kamalika Chaudhuri and Daniel Hsu. Convergence rates for differentially private statistical estimation. In Proceedings of the 29th International Conference on Machine Learning (ICML), volume 2012, page 1327, 2012. Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3–37, 2022. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3-4):211–487, 2014. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486–503. Springer, 2006a. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis, pages 265–284. Springer Berlin Heidelberg, 2006b. ISBN 9783540327325. doi: 10.1007/11681878_14. Vitaly Feldman and David Xiao. Sample complexity bounds on differentially private learning via communication complexity. SIAM Journal on Computing, 44(6):1740–1764, 2015. Fengyu Gao, Ruida Zhou, Tianhao Wang, Cong Shen, and Jing Yang. Data-adaptive differentially private prompt synthesis for in-context learning. In The Fourteenth International Conference on Learning Representations (ICLR), 2025. Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, and Chiyuan Zhang. User-level differential privacy with few examples per user. In Advances in Neural Information Processing Systems (NeurIPS), 2023. E. Mark Gold. Language identification in the limit. Information and Control, 10(5):447–474, 1967.

Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, and Huanyu Zhang. Locally private hypothesis selection. In Proceedings of the Thirty-Third Conference on Learning Theory (COLT), pages 1785–1816. PMLR, 2020. Steve Hanneke, Amin Karbasi, Anay Mehrotra, and Grigoris Velegkas. On union-closedness of language generation. In Advances in Neural Information Processing Systems (NeurIPS), 2025. Mikael Møller Høgsgaard and Chirag Pabbaraju. Agnostic language identification and generation. arXiv preprint arXiv:2601.23258, 2026. 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), pages 1732–1743. ACM, 2025. doi: 10.1145/3717823.3718108. Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. On characterizations for language generation: Interplay of hallucinations, breadth, and stability. In Proceedings of the International Conference on Algorithmic Learning Theory (ALT), 2026. Amin Karbasi, Omar Montasser, John Sous, and Grigoris Velegkas. (Im)possibility of automated hallucination detection in large language models. In Conference on Language Modeling (COLM), 2025. Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793–826, 2011. Jon Kleinberg and Sendhil Mullainathan. Language generation in the limit. In Advances in Neural Information Processing Systems (NeurIPS), volume 37, pages 66058–66079, 2024. Jon Kleinberg and Fan Wei. Language generation and identification from partial enumeration: Tight density bounds and topological characterizations. arXiv preprint arXiv:2511.05295, 2025a. Jon Kleinberg and Fan Wei. Density measures for language generation. In Proceedings of the 66th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2025b. Jon Kleinberg and Fan Wei. Banach density of generated languages: Dichotomies in topology and dimension. arXiv preprint arXiv:2604.02385, 2026. Steffen Lange, Thomas Zeugmann, and Sandra Zilles. Learning indexed families of recursive languages from positive data: A survey. Theoretical Computer Science, 397(1-3):194–232, 2008. Daniel Levy, Ziteng Sun, Kareem Amin, Satyen Kale, Alex Kulesza, Mehrdad Agarwal, and Peter Kairouz. Learning with user-level privacy. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, 2021. Aaron Li and Ian Zhang. Quantifying noise in language generation. arXiv preprint arXiv:2601.21237, 2026. Jiaxun Li, Vinod Raman, and Ambuj Tewari. On generation in metric spaces. arXiv preprint arXiv:2602.07710, 2026. Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. Large language models can be strong differentially private learners. In International Conference on Learning Representations (ICLR), 2022. Ruixuan Liu and Zhiqi Bu. Towards hyperparameter-free optimization with differential privacy. In The Fourteenth International Conference on Learning Representations (ICLR), 2025. 15

Yuhan Liu, Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, and Michael Riley. Learning discrete distributions: User vs. item-level privacy. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020. Bartłomiej Marek, Lorenzo Rossi, Vincent Hanke, Xun Wang, Michael Backes, Franziska Boenisch, and Adam Dziedzic. Benchmarking empirical privacy protection for adaptations of large language models. In The Fourteenth International Conference on Learning Representations (ICLR), 2026. Ryan McKenna, Yangsibo Huang, Amer Sinha, Borja Balle, Zachary Charles, Christopher A. ChoquetteChoo, Badih Ghazi, Georgios Kaissis, Ravi Kumar, Ruibo Liu, Da Yu, and Chiyuan Zhang. Scaling laws for differentially private language models. In Forty-second International Conference on Machine Learning (ICML), 2025. Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 94–103. IEEE, 2007. Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. Language generation with infinite contamination. arXiv preprint arXiv:2511.07417, 2025. Ilya Mironov. Rényi differential privacy. In Proceedings of the 30th IEEE Computer Security Foundations Symposium (CSF), pages 263–275, 2017. Hristo Papazov and Nicolas Flammarion. Learning algorithms in the limit. In The Thirty-Eighth Annual Conference on Learning Theory (COLT), pages 4486–4510. PMLR, 2025. Charlotte Peale, Vinod Raman, and Omer Reingold. Representative language generation. In Proceedings of the 42nd International Conference on Machine Learning (ICML). PMLR, 2025. Binghui Peng, Amin Saberi, and Grigoris Velegkas. Language identification in the limit with computational trace. In The Fourteenth International Conference on Learning Representations (ICLR), 2026. Natalia Ponomareva, Sergei Vassilvitskii, Zheng Xu, Brendan McMahan, Alexey Kurakin, and Chiyaun Zhang. How to DP-fy ML: A practical tutorial to machine learning with differential privacy. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 5823–5824, 2023. Natalia Ponomareva, Zheng Xu, H Brendan McMahan, Peter Kairouz, Lucas Rosenblatt, Vincent CohenAddad, Cristóbal Guzmán, Ryan McKenna, Galen Andrew, Alex Bie, et al. How to DP-fy your data: A practical guide to generating synthetic data with differential privacy. arXiv preprint arXiv:2512.03238, 2025. Giorgio Racca, Michal Valko, and Amartya Sanyal. Language generation with replay: A learning-theoretic view of model collapse. arXiv preprint arXiv:2603.11784, 2026. Ananth Raman and Vinod Raman. Generation from noisy examples. In Proceedings of the 42nd International Conference on Machine Learning (ICML), volume 267 of Proceedings of Machine Learning Research. PMLR, 2025. Vinod Raman, Jiaxun Li, and Ambuj Tewari. Generation through the lens of learning theory. In Proceedings of the Thirty-Eighth Conference on Learning Theory (COLT), pages 4740–4776. PMLR, 2025. Tom Sander, Pierre Stock, and Alexandre Sablayrolles. TAN without a burn: Scaling laws of DP-SGD. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 29937–29949. PMLR, 2023. 16

Adam Smith. Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 813–822, 2011. Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality, 7(2), 2017. Rushil Thareja, Preslav Nakov, Praneeth Vepakomma, and Nils Lukas. DP-fusion: Token-level differentially private inference for large language models. In The Fourteenth International Conference on Learning Representations (ICLR), 2026. Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019. Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A. Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, Sergey Yekhanin, and Huishuai Zhang. Differentially private fine-tuning of language models. In International Conference on Learning Representations (ICLR), 2022. Xiang Yue, Huseyin A. Inan, Xuechen Li, Girish Kumar, Julia McAnallen, Hoda Shajari, Huan Sun, David Levitan, and Robert Sim. Synthetic text generation with differential privacy: A simple and practical recipe. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (ACL), pages 1321–1342. Association for Computational Linguistics, 2023.

Appendix Organization of the Appendix. Section A provides additional related work. Section B collects concentration inequalities and privacy tools used throughout. Section C reviews the non-private algorithms. Section D contains the full proofs for the DP identification upper bounds. Section E contains the full proofs for the DP generation upper bounds. Section F contains the full proofs for the lower bounds.

Additional Related Work

Language Identification. Lange et al. [2008] provided a comprehensive survey of the identificationin-the-limit paradigm. Charikar et al. [2025] studied list identification, showing that allowing 𝑘 guesses per step strictly expands identifiability. Peng et al. [2026] showed that augmenting Gold’s paradigm with computational traces enables identification of all recursively enumerable languages. Papazov and Flammarion [2025] extend Gold’s inductive inference framework with computational observations and restricted input sources to study learnability of computable functions in the limit. Language Generation. Following Kleinberg and Mullainathan [2024], Raman et al. [2025] placed generation within a broader learning-theoretic hierarchy. The tension between output diversity and hallucination was examined by Kalavasis et al. [2025, 2026], Charikar and Pabbaraju [2025], Peale et al. [2025], and Kleinberg and Wei [2025b,a, 2026], with Pareto-optimal tradeoffs studied by Charikar and Pabbaraju [2026]. Robustness under noise models was studied by Raman and Raman [2025], Bai et al. [2026], Mehrotra et al. [2025], and Li and Zhang [2026]. On the structural side, Hanneke et al. [2025] and Bai et al. [2026] showed that generatability is not closed under finite unions for uncountable collections, and Karbasi et al. [2025] investigated automated hallucination detection. Computational and sample-complexity barriers were analyzed by Arenas et al. [2025]. More recent extensions include generation in continuous metric spaces [Li et al., 2026] and safe generation [Anastasopoulos et al., 2026]. Racca et al. [2026] study model collapse from a learning-theoretic perspective, showing replay creates provable separations for weaker notions of language generation. Private Learning and Language Models. There is a rich literature on differentially private PAC learning [Kasiviswanathan et al., 2011; Bun et al., 2015; Bun, 2020] and private statistical estimation [Chaudhuri and Hsu, 2012; Aden-Ali et al., 2021; Bie et al., 2022]. On the applied side, Abadi et al. [2016] introduced DP-SGD, which has been extensively applied to large-scale language model training and fine-tuning [Anil et al., 2022; Yu et al., 2022; Li et al., 2022]. Ponomareva et al. [2023] provided a comprehensive practical guide to training machine learning models with differential privacy. Sander et al. [2023] studied scaling laws for private training, Yue et al. [2023] developed practical recipes for private synthetic text generation, Ghazi et al. [2023] studied user-level privacy with few examples per user, and Ponomareva et al. [2025] provided a practical guide to DP synthetic data generation. Gao et al. [2025] proposed a data-adaptive framework that synthesizes differentially private few-shot demonstrations for in-context learning with LLMs, improving the privacy–utility tradeoff without requiring public data. Liu and Bu [2025] proposed a hyperparameter-free DP training framework that eliminates the need for manually tuning the clipping threshold in DP-SGD, reducing the computational overhead of private fine-tuning for large language models. Marek et al. [2026] benchmark the practical privacy protection of DP-adapted LLMs via membership inference and canary extraction attacks. Thareja et al. [2026] DP-Fusion, a token-level differentially private inference mechanism for LLMs that bounds the influence of sensitive context tokens on the model’s output. These works focus on empirical sides, whereas we establish information-theoretic guarantees. To our knowledge, ours is the first work to study differential privacy in this theoretical framework of language identification and generation. 18

Useful Lemmas

B.1

Concentration Inequalities

We state some standard concentration inequalities and tail bounds; see, e.g., Boucheron et al. [2013]; Vershynin [2018]; Wainwright [2019] for comprehensive references. Í Lemma B.1 (Hoeffding’s Inequality). Let 𝑋 = 𝑛1 𝑛𝑖=1 𝑋𝑖 be the average of 𝑛 independent random variables taking values in [𝑎, 𝑏], and let 𝜇 = 𝐸 [𝑋 ]. For any 𝑡 ≥ 0, we have 2𝑛 2𝑡 2 Pr[|𝑋 − 𝜇| ≥ 𝑡] ≤ 2 exp − . (𝑏 − 𝑎) 2 Í Lemma B.2 (Chernoff Bounds). Let 𝑋 = 𝑛1 𝑛𝑖=1 𝑋𝑖 be the average of 𝑛 independent random variables taking values in [0, 1], and let 𝜇 = 𝐸 [𝑋 ]. For any 𝑡 ≥ 0, 𝑛𝜇𝑡 2 . 𝑃 (𝑋 ≤ (1 − 𝑡)𝜇) ≤ exp − 2 For any 𝑡 ∈ [0, 1], 𝑛𝜇𝑡 2 𝑃 (𝑋 ≥ (1 + 𝑡)𝜇) ≤ exp − . 3 Lemma B.3 (Gaussian Tail Bounds). If 𝑍 ∼ N (0, 𝜎 2 ), then for every 𝑡 ≥ 0, we have 𝑡2 𝑡2 Pr[𝑍 ≥ 𝑡] ≤ exp − 2 and Pr[|𝑍 | ≥ 𝑡] ≤ 2 exp − 2 . 2𝜎 2𝜎

B.2

Tools from Differential Privacy

Lemma B.4 (Group Privacy Dwork and Roth [2014]). Let A : U𝑛 → R be 𝜀-differentially private. If 𝑆, 𝑆 ′ ∈ U𝑛 differ in at most 𝑘 entries, then for every measurable F ⊆ R, we have Pr[A (𝑆) ∈ F ] ≤ exp(𝜀𝑘) Pr[A (𝑆 ′ ) ∈ F ], where the probability is taken over the randomness of A. Lemma B.5 (Coupling Lemma via Group Privacy, a Variant of Lemma 19 in Acharya et al. [2021]). Let A : U𝑛 → R be 𝜀-differentially private. Let (𝑆, 𝑆 ′ ) be a coupling of two distributions over U𝑛 such that Pr[𝑑 Ham (𝑆, 𝑆 ′ ) > 𝐾] ≤ 𝜂 for some 𝐾 ≥ 0 and 𝜂 ∈ [0, 1], where 𝑑 Ham is Hamming distance. Then for every measurable set F ⊆ R, we have Pr [A (𝑆) ∈ F ] ≤ exp(𝜀𝐾) Pr [A (𝑆 ′ ) ∈ F ] + 𝜂. ′

𝑆,𝑟

𝑆 ,𝑟

Proof. Let 𝐺 := {𝑑 Ham (𝑆, 𝑆 ′ ) ≤ 𝐾 } so that Pr[𝐺 𝑐 ] ≤ 𝜂. Then Pr[A (𝑆) ∈ F ] ≤ Pr[A (𝑆) ∈ F | 𝐺] + Pr[𝐺 𝑐 ]. Conditioning on 𝐺, we have 𝑑 Ham (𝑆, 𝑆 ′ ) ≤ 𝐾. Hence Lemma B.4 gives, pointwise, Pr [A (𝑆) ∈ F | 𝑆, 𝑆] ≤ 𝑒 𝜀𝐾 Pr [A (𝑆 ′ ) ∈ F | 𝑆, 𝑆 ′ ]. 𝑟

𝑟

Taking expectation over (𝑆, 𝑆 ′ ) yields Pr[A (𝑆) ∈ F | 𝐺] ≤ 𝑒 𝜀𝐾 Pr[A (𝑆 ′ ) ∈ F ]. Combining with Pr[𝐺 𝑐 ] ≤ 𝜂 completes the proof.

□ 19

Non-Private Algorithms for Language Identification and Generation

For completeness, we restate the non-private algorithms of Høgsgaard and Pabbaraju [2026] that serve as the starting points for our private constructions. Algorithm 4 performs agnostic identification via a margin-based selection rule: it selects the largestindexed language within a growing horizon [𝑓 (𝑛)] that beats all predecessors in empirical risk by a margin of 2/𝑓 (𝑛). Algorithm 4 Non-Private Agnostic Identification [Høgsgaard and Pabbaraju, 2026] Require: A dataset 𝑆 = (𝑥 1, . . . , 𝑥𝑛 ) ∈ U𝑛 , a function 𝑓 : ℕ → ℕ with 𝑓 (𝑛) → ∞, a language collection C = {𝐿1, 𝐿2, . . .} Ensure: A language 𝐿𝐴(𝑆 ) ∈ C 1: for 𝑖 ∈ [𝑓 (𝑛)] do Í 2: err𝑆 (𝐿𝑖 ) ← 𝑛1 𝑛𝑡=1 1{𝑥𝑡 ∉ 𝐿𝑖 } 3: end for 2 4: 𝐴(𝑆) ← largest index 𝑖 ∈ [𝑓 (𝑛)] such that err𝑆 (𝐿 𝑗 ) − err𝑆 (𝐿𝑖 ) > 𝑓 (𝑛) for all 𝑗 < 𝑖 5: return 𝐿𝐴(𝑆 ) Algorithm 5 performs agnostic generation via a pointer-based rule: for each language, it maintains a pointer to the smallest-indexed string not yet seen in the sample, and selects the language whose pointer has advanced the farthest. Note that the original presentation in Høgsgaard and Pabbaraju [2026] iterates over all 𝑖 ∈ ℕ. We restrict to a finite horizon [𝑓 (𝑛)] with 𝑓 (𝑛) → ∞. This is without loss of generality since 𝑓 (𝑛) ≥ 𝑖 ★ for all sufficiently large 𝑛, and it is necessary for our privatization. Algorithm 5 Non-Private Agnostic Generation [Høgsgaard and Pabbaraju, 2026] Require: A dataset 𝑆 = (𝑥 1, . . . , 𝑥𝑛 ) ∈ U𝑛 , a function 𝑓 : ℕ → ℕ with 𝑓 (𝑛) → ∞, a language collection C = {𝐿1, 𝐿2, . . .} Ensure: A string 𝑥b ∈ U 1: for 𝑖 ∈ [𝑓 (𝑛)] do 2: 𝑟𝑖 ← min{𝑘 ∈ ℕ : 𝑢𝑘 ∈ 𝐿𝑖 } ⊲ Initialize pointer to first string in 𝐿𝑖 3: end for 4: for 𝑖 ∈ [𝑓 (𝑛)] do 5: while ∃ 𝑡 ∈ [𝑛] : 𝑥𝑡 = 𝑢𝑟𝑖 do 6: 𝑟𝑖 ← min{𝑘 ∈ ℕ : 𝑢𝑘 ∈ 𝐿𝑖 , 𝑘 > 𝑟𝑖 } ⊲ Advance pointer past seen strings 7: end while 8: end for 9: 𝑜 ← arg max𝑖 ∈ [ 𝑓 (𝑛) ] 𝑟 𝑖 ⊲ Select language with largest pointer 10: return any novel string from 𝐿𝑜 The key challenge in privatizing these algorithms is that their score functions have very different sensitivity properties. The identification margin test (Algorithm 4, line 4) is discontinuous: changing a single sample can flip which indices satisfy the margin constraint. The generation pointer (Algorithm 5, lines 5–7) has unbounded sensitivity: removing the sole occurrence of some 𝑢𝑘 from the sample can reset the pointer from beyond the witness window back to 𝑘, an arbitrary jump. Our private algorithms resolve these issues by replacing both rules with smooth score functions amenable to the exponential and Gaussian mechanisms.

Proofs for Section 3 (Upper Bounds for DP Identification)

Assumption D.1 (Agnostic Optimum is Attainable). There exists an index 𝑖 ★ ∈ ℕ such that err𝑆 (𝐿𝑖★ ) = inf 𝐿∈ C err D (𝐿𝑖 ). Let 𝑖 ★ denote the smallest such index. When 𝑖 ★ > 1, we define the least risk gap between 𝑖 ★ and the earlier indices as ★ ) > 0. 𝑐 gap := min err (𝐿 ) − err (𝐿 D 𝑗 D 𝑖 ★ 𝑗 ∈ [𝑖 −1]

(D.1)

Let 𝑓 : ℕ → ℕ be a function with 𝑓 (𝑛) → ∞. There exists 𝑛 0 (depending on C, D, 𝑓 ) such that for all 𝑛 ≥ 𝑛 0 , we have (i) 𝑚 ≥ 𝑖 ★

(the optimal language is within the horizon).

(ii) 𝑚 ≥ 3/𝑐 gap if 𝑖 ★ > 1

(the margin threshold 2/𝑚 is smaller than the gap).

All results below assume 𝑛 ≥ 𝑛 0 without further mention.

D.1

Proof of Theorem 3.2 (Pure DP Identification)

For 𝑆 ∈ U𝑛 , 𝑖 ∈ [𝑓 (𝑛)], we define the margin ( 1, 𝑀𝑆 (𝑖) := min 𝑗 ∈ [𝑖 −1] err𝑆 (𝐿 𝑗 ) − err𝑆 (𝐿𝑖 ) ,

if 𝑖 = 1, if 𝑖 ≥ 2,

(D.2)

the deficit 2 − 𝑀𝑆 (𝑖) , + 𝑓 (𝑛)

(D.3)

𝑞(𝑆, 𝑖) := 𝑖 − 𝑓 (𝑛) 2𝑑𝑆 (𝑖).

(D.4)

𝑑𝑆 (𝑖) := and the score

D.1.1

Privacy Analysis

The privacy proof follows directly from the exponential mechanism once we bound the sensitivity of the score function. Lemma D.2 (Sensitivity of the Score Function). The score function 𝑞 defined in (D.4) has sensitivity 2𝑚 2 /𝑛. That is, for any neighboring 𝑆, 𝑆 ′ ∈ U𝑛 and any 𝑖 ∈ [𝑓 (𝑛)], we have |𝑞(𝑆, 𝑖) − 𝑞(𝑆 ′, 𝑖)| ≤

2𝑚 2 . 𝑛

Í Proof. Let 𝑆, 𝑆 ′ ∈ U𝑛 be two neighboring datasets. Since each err𝑆 (𝐿 𝑗 ) = 𝑛1 𝑛𝑡=1 1{𝑥𝑡 ∉ 𝐿 𝑗 } is an average of 𝑛 binary indicators, changing one element in a dataset changes at most one indicator, so for 𝑗 ∈ [𝑓 (𝑛)], we have |err𝑆 (𝐿 𝑗 ) − err𝑆 ′ (𝐿 𝑗 )| ≤

1 . 𝑛

(D.5)

For 𝑖 ≥ 2, define Δ 𝑗,𝑖 (𝑆) := err𝑆 (𝐿 𝑗 ) − err𝑆 (𝐿𝑖 ). By the triangle inequality and (D.5), we have |Δ 𝑗,𝑖 (𝑆) − Δ 𝑗,𝑖 (𝑆 ′ )| ≤ 2/𝑛. Since the pointwise minimum of functions preserves Lipschitz constants, it holds that |𝑀𝑆 (𝑖) − 𝑀𝑆 ′ (𝑖)| ≤ 21

2 . 𝑛

(D.6)

2 2𝑚 2 = . 𝑛 𝑛 □

Lemma D.3 (Privacy). Algorithm 1 is 𝜀-differentially private. Proof. The only data-dependent output is b 𝑖 , produced by the exponential mechanism with score 𝑞 over range [𝑚]. By Lemma D.2, 𝑞 has sensitivity Δ = 2𝑚 2 /𝑛. The exponential mechanism guarantee (Lemma 2.4) yields 𝜀-DP. □ D.1.2

Utility Analysis

The utility analysis proceeds in three steps: (i) a uniform concentration event E under which all empirical errors in the horizon are close to their population values (Lemma D.4); (ii) on E, the optimal index 𝑖 ★ is the unique maximizer of the score function with a gap of at least 1 (Lemma D.6); (iii) the exponential mechanism exploits this gap to select 𝑖 ★ with high probability (Lemma D.7). Lemma D.4 (Uniform Concentration). Define the event n E := err𝑆 (𝐿𝑖 ) − err D (𝐿𝑖 ) ≤

1 , 4𝑓 (𝑛)

o ∀𝑖 ∈ [𝑓 (𝑛)] .

Then Pr𝑆∼D𝑛 [E𝑐 ] ≤ 2𝑓 (𝑛) exp −𝑛/(8𝑓 (𝑛) 2 ) . Proof. For each 𝑖 ∈ [𝑓 (𝑛)], Hoeffding’s inequality (Lemma B.1) gives h Pr |err𝑆 (𝐿𝑖 ) − err D (𝐿𝑖 )| >

1 i 𝑛 𝑛 ≤ 2 exp −2 · = 2 exp − . 4𝑓 (𝑛) 16𝑓 (𝑛) 2 8𝑓 (𝑛) 2

A union bound over [𝑓 (𝑛)] yields Pr[E𝑐 ] ≤

𝑓∑︁ (𝑛)

2 exp −

𝑖=1

𝑛 𝑛 = 2𝑓 (𝑛) exp − . 8𝑓 (𝑛) 2 8𝑓 (𝑛) 2 □

Remark D.5 (Choice of Precision 1/(4𝑓 (𝑛))). We choose the precision 1/(4𝑓 (𝑛)) so that on E: for 𝑗 < 𝑖 ★, the empirical margin err 𝑗 (𝑆) − err𝑖★ remains above 2/𝑓 (𝑛), ensuring 𝑖 ★ passes the margin test; for 𝑖 > 𝑖 ★, the empirical margin err𝑆 (𝐿𝑖★ ) − err𝑆 (𝐿𝑖 ) is at most 1/(2𝑓 (𝑛)) < 2/𝑓 (𝑛), ensuring such 𝑖 fail the margin test. In fact, any precision 𝜂 satisfying 𝜂 < 𝑐 gap /2 and 2𝜂 < 2/𝑓 (𝑛) would work; 1/(4𝑓 (𝑛)) is a convenient choice that satisfies both since 𝑓 (𝑛) ≥ 3/𝑐 gap . Lemma D.6 (Score separation on E). On the event E, we have (a) 𝑞(𝑆, 𝑖 ★) = 𝑖 ★. (b) 𝑞(𝑆, 𝑖) ≤ 𝑖 ★ − 1 for every 𝑖 ∈ [𝑓 (𝑛)] \ {𝑖 ★ }. Consequently, OPT𝑞 (𝑆) = 𝑖 ★ and the score gap is at least 1. 22

Proof. Assume E holds throughout. Case 1: 𝑞(𝑆, 𝑖 ★) = 𝑖 ★. We show 𝑑𝑆 (𝑖 ★) = 0, i.e., 𝑀𝑆 (𝑖 ★) ≥ 2/𝑓 (𝑛). If 𝑖 ★ = 1, then 𝑀𝑆 (1) = 1 ≥ 2/𝑓 (𝑛), so 𝑑𝑆 (1) = 0 and 𝑞(𝑆, 1) = 1 = 𝑖 ★. If 𝑖 ★ ≥ 2, then for every 𝑗 < 𝑖 ★, we have err D (𝐿 𝑗 ) − err D (𝐿𝑖★ ) ≥ 𝑐 gap ≥ 3/𝑓 (𝑛), where the last inequality uses 𝑓 (𝑛) ≥ 3/𝑐 gap . On E, each empirical risk deviates from the corresponding population risk by at most 1/(4𝑓 (𝑛)), so 3 1 5 2 2 ≥ − = > . err𝑆 (𝐿 𝑗 ) − err𝑆 (𝐿𝑖★ ) ≥ err D (𝐿 𝑗 ) − err D (𝐿𝑖★ ) − 4𝑓 (𝑛) 𝑓 (𝑛) 2𝑓 (𝑛) 2𝑓 (𝑛) 𝑓 (𝑛) Taking the minimum over 𝑗 < 𝑖 ★ gives 𝑀𝑆 (𝑖 ★) ≥ 5/(2𝑓 (𝑛)) > 2/𝑓 (𝑛), hence 𝑑𝑆 (𝑖 ★) = 0 and 𝑞(𝑆, 𝑖 ★) = 𝑖 ★. Case 2: 𝑞(𝑆, 𝑖) ≤ 𝑖 ★ − 1 for 𝑖 < 𝑖 ★. Since 𝑑𝑆 (𝑖) ≥ 0, we have 𝑞(𝑆, 𝑖) = 𝑖 − 𝑓 (𝑛) 2𝑑𝑆 (𝑖) ≤ 𝑖 ≤ 𝑖 ★ − 1 Case 3: 𝑞(𝑆, 𝑖) ≤ 𝑖 ★ − 1 for 𝑖 > 𝑖 ★. By the optimality of 𝑖 ★, we have err D (𝐿𝑖 ) ≥ err D (𝐿𝑖★ ). On E, 1 1 − err D (𝐿𝑖 ) − err𝑆 (𝐿𝑖★ ) − err𝑆 (𝐿𝑖 ) ≤ err D (𝐿𝑖★ ) + 4𝑓 (𝑛) 4𝑓 (𝑛) 1 1 = err D (𝐿𝑖★ ) − err D (𝐿𝑖 ) + ≤ . 2𝑓 (𝑛) 2𝑓 (𝑛) Since 𝑗 = 𝑖 ★ is among the candidates in the minimum defining 𝑀𝑆 (𝑖), we obtain 𝑀𝑆 (𝑖) ≤ 1/(2𝑓 (𝑛)) < 2/𝑓 (𝑛). Therefore 𝑑𝑆 (𝑖) =

2 2 1 3 − 𝑀𝑆 (𝑖) ≥ − = , 𝑓 (𝑛) 𝑓 (𝑛) 2𝑓 (𝑛) 2𝑓 (𝑛)

and the score satisfies 𝑞(𝑆, 𝑖) = 𝑖 − 𝑓 (𝑛) 2 · 𝑑𝑆 (𝑖) ≤ 𝑖 − 𝑓 (𝑛) 2 ·

3𝑓 (𝑛) 3𝑓 (𝑛) 𝑓 (𝑛) 3 =𝑖 − ≤ 𝑓 (𝑛) − =− ≤ 𝑖 ★ − 1. 2𝑓 (𝑛) 2 2 2 □

Lemma D.7 (Private Selection). Define 𝜀𝑛 𝛽 := exp − . 8𝑓 (𝑛) 2 If 𝛽 < 1, on the event E, the Algorithm 1 outputs b 𝑖 = 𝑖 ★ with probability at least 1 − 𝛽. Proof. On E, Lemma D.6 gives OPT𝑞 (𝑆) = 𝑖 ★ and 𝑞(𝑆, 𝑖) ≤ 𝑖 ★ − 1 for all 𝑖 ≠ 𝑖 ★. By the utility guarantee of the exponential mechanism (Lemma 2.4) with sensitivity Δ = 2𝑓 (𝑛) 2 /𝑛 (Lemma D.2) and range |R| = 𝑓 (𝑛), with probability at least 1 − 𝛽 the output b 𝑖 satisfies 𝑞(𝑆, b 𝑖 ) ≥ OPT𝑞 (𝑆) −

𝑓 (𝑛) 2Δ log . 𝜀 𝛽

Substituting 𝛽 = 𝑓 (𝑛) exp(−𝜀𝑛/(8𝑓 (𝑛) 2 )), we compute log

𝑓 (𝑛) 𝑓 (𝑛) 𝜀𝑛 = log = , 2 𝛽 𝑓 (𝑛) exp(−𝜀𝑛/(8𝑓 (𝑛) )) 8𝑓 (𝑛) 2

and therefore 𝑓 (𝑛) 2 · 2𝑓 (𝑛) 2 /𝑛 2Δ 𝜀𝑛 1 log = · = . 2 𝜀 𝛽 𝜀 8𝑓 (𝑛) 2 This gives 𝑞(𝑆, b 𝑖 ) ≥ 𝑖 ★ − 1/2. Since every 𝑖 ≠ 𝑖 ★ satisfies 𝑞(𝑆, 𝑖) ≤ 𝑖 ★ − 1 < 𝑖 ★ − 1/2 on E, we conclude b 𝑖 = 𝑖★ with probability at least 1 − 𝛽. □ 23

D.1.3

Putting Things Together

Theorem D.8 (Guarantees of Algorithm 1). Let C = {𝐿𝑖 }𝑖 ∈ℕ be a countable collection of languages and let D be any distribution over U. Suppose Assumption D.1 holds. Let 𝜀 > 0 and let 𝑓 : ℕ → ℕ satisfy 𝑓 (𝑛) → ∞. Then for all sufficiently large 𝑛, Algorithm 1 has the following guarantees: • Privacy. Algorithm 1 is 𝜀-differentially private. • Utility. The identification error satisfies id IdErr(A𝜀,𝑓 , D, C, 𝑛) ≤ 2𝑓 (𝑛) exp −

𝜀𝑛 𝑛 + 𝑓 (𝑛) exp − . 8𝑓 (𝑛) 2 8𝑓 (𝑛) 2

(D.7)

Proof. Privacy. This directly follows from Lemma D.3. Utility. We note that the excess error err D (𝐿b𝑖 ) − inf 𝐿∈ C err D (𝐿) lies in [0, 1] and equals 0 when b 𝑖 = 𝑖 ★. Therefore id IdErr(A𝜀,𝑓 , D, C, 𝑛) = 𝔼 err D (𝐿b𝑖 ) − inf err D (𝐿) ≤ Pr [b 𝑖 ≠ 𝑖 ★]. 𝐿∈ C

𝑆,𝑟

We decompose using the event E from Lemma D.4: Pr[b 𝑖 ≠ 𝑖 ★] = Pr[b 𝑖 ≠ 𝑖 ★ | E] Pr[E] + Pr[b 𝑖 ≠ 𝑖 ★ | E𝑐 ] Pr[E𝑐 ] ≤ Pr[b 𝑖 ≠ 𝑖 ★ | E] + Pr[E𝑐 ]. Applying Lemma D.7 and Lemma D.4: 𝑛 𝜀𝑛 + 2𝑓 (𝑛) exp − . Pr[b 𝑖 ≠ 𝑖 ★] ≤ 𝑓 (𝑛) exp − 8𝑓 (𝑛) 2 8𝑓 (𝑛) 2 □ Corollary D.9 (Explicit Rates). The bound (D.7) yields different rates depending on the choice of horizon 𝑓 : √︁ • 𝑓 (𝑛) = 𝑐 log 𝑛 for sufficiently large 𝑐 > 0: √︁ min{1, 𝜀} · 𝑛 min{1, 𝜀} · 𝑛 id IdErr(A𝜀,𝑓 , D, C, 𝑛) ≤ 𝑂 log 𝑛 · exp − ≲ exp − . 8𝑐 log 𝑛 log 𝑛 • 𝑓 (𝑛) = 𝑛𝛼 for 𝛼 ∈ (0, 1/2): id IdErr(A𝜀,𝑓 , D, C, 𝑛) ≤ 𝑂 (𝑛𝛼 ) · exp

min{1, 𝜀} · 𝑛 1−2𝛼 − ≲ exp − min{1, 𝜀} · 𝑛 1−2𝛼 . 8

√︁ • 𝑓 (𝑛) = 𝑐 · 𝑛/𝑟 (𝑛) for any 𝑟 (𝑛) = 𝑜 (𝑛) with 𝑟 (𝑛) → ∞: id IdErr(A𝜀,𝑓 , D, C, 𝑛) ≲ exp (− min{1, 𝜀} · 𝑟 (𝑛)) .

D.2

Proof of Theorem 3.3 (Approximate DP Identification)

For the noisy empirical errors ef rr𝑆 (𝐿𝑖 ) := err𝑆 (𝐿𝑖 ) + 𝑍𝑖 , we define the noisy margin ( if 𝑖 = 1, e𝑆 (𝑖) := 1, 𝑀 min 𝑗 ∈ [𝑖 −1] ef rr𝑆 (𝐿 𝑗 ) − ef rr𝑆 (𝐿𝑖 ) , if 𝑖 ≥ 2. 24

(D.8)

D.2.1

Privacy Analysis

Lemma D.10 (ℓ2 -Sensitivity of the Empirical Error Vector). Define 𝑣 : U𝑛 → ℝ 𝑓 (𝑛) by 𝑣 (𝑆) := err𝑆 (𝐿1 ), . . . , err𝑆 (𝐿 𝑓 (𝑛) ) . √︁ Then 𝑣 has ℓ2 -sensitivity 𝑓 (𝑛)/𝑛. Proof. For neighboring 𝑆, 𝑆 ′ ∈ U𝑛 , by (D.5), we have |err𝑆 (𝐿𝑖 ) − err𝑆 ′ (𝐿𝑖 )| ≤ 1/𝑛 for each 𝑖 ∈ [𝑓 (𝑛)]. Therefore ∥𝑣 (𝑆) − 𝑣 (𝑆 ′ ) ∥ 22 =

𝑓∑︁ (𝑛)

err𝑆 (𝐿𝑖 ) − err𝑆 ′ (𝐿𝑖 ) ≤

𝑖=1

Taking the square root gives ∥𝑣 (𝑆) − 𝑣 (𝑆 ′ ) ∥ 2 ≤

√︁

𝑓∑︁ (𝑛)

𝑓 (𝑛) 1 = 2 . 2 𝑛 𝑛 𝑖=1

𝑓 (𝑛)/𝑛.

□

Lemma D.11 (Privacy). Algorithm 2 is (𝜀, 𝛿)-differentially private. √︁ Proof. By Lemma D.10, the empirical error vector has ℓ2 -sensitivity Δ2 = 𝑓 (𝑛)/𝑛. The Gaussian mech√ √︁ 𝑓 (𝑛) √︁ anism (Lemma 2.5) with 𝜎 = Δ𝜀2 2 log(1.25/𝛿) = 𝜀𝑛 2 log(1.25/𝛿) ensures that the noisy vector ef rr𝑆 (𝐿1 ), . . . , ef rr𝑆 (𝐿 𝑓 (𝑛) ) is (𝜀, 𝛿)-differentially private. The subsequent margin selection (line 9 of Algorithm 2) is a deterministic function of this noisy vector and is therefore (𝜀, 𝛿)-DP by post-processing (Lemma 2.3). □ D.2.2

Utility Analysis

The utility analysis proceeds in three steps: (i) a uniform concentration event E under which all empirical errors in the horizon are close to their population values (Lemma D.4); (ii) a noise concentration event F under which the Gaussian perturbations are small (Lemma D.12); (iii) on E ∩ F , the deterministic margin-selection rule outputs 𝑖 ★ (Lemma D.13). Lemma D.12 (Noise Concentration). Define the event n 1 F := |𝑍𝑖 | ≤ , 4𝑓 (𝑛)

o ∀𝑖 ∈ [𝑓 (𝑛)] .

Then 𝜀 2𝑛 2 Pr[F ] ≤ 2𝑓 (𝑛) exp − . 64𝑓 (𝑛) 3 log(1.25/𝛿) 𝑐

Proof. Each 𝑍𝑖 ∼ N (0, 𝜎 2 ) with 𝜎 2 = 𝑖 ∈ [𝑓 (𝑛)], h Pr |𝑍𝑖 | >

2𝑓 (𝑛) log(1.25/𝛿 ) . By the Gaussian tail bound (Lemma B.3), for each 𝜀 2𝑛 2

1/(16𝑓 (𝑛) 2 ) 1 i 𝜀 2𝑛 2 ≤ 2 exp − = 2 exp − . 4𝑓 (𝑛) 2𝜎 2 64𝑓 (𝑛) 3 log(1.25/𝛿)

A union bound over 𝑖 ∈ [𝑓 (𝑛)] yields Pr[F 𝑐 ] ≤

𝑓∑︁ (𝑛) 𝑖=1

2 exp −

𝜀 2𝑛 2 𝜀 2𝑛 2 = 2𝑓 (𝑛) exp − . 64𝑓 (𝑛) 3 log(1.25/𝛿) 64𝑓 (𝑛) 3 log(1.25/𝛿) □ 25

Lemma D.13 (Deterministic Correctness on E ∩ F ). On the event E ∩ F , Algorithm 2 outputs b 𝑖 = 𝑖 ★. Proof. Assume E ∩ F holds throughout. Since ef rr𝑆 (𝐿𝑖 ) = err𝑆 (𝐿𝑖 ) + 𝑍𝑖 , the triangle inequality gives ef rr𝑆 (𝐿𝑖 ) − err D (𝐿𝑖 ) ≤ err𝑆 (𝐿𝑖 ) − err D (𝐿𝑖 ) + |𝑍𝑖 | ≤

1 1 1 + = 4𝑓 (𝑛) 4𝑓 (𝑛) 2𝑓 (𝑛)

(D.9)

for all 𝑖 ∈ [𝑓 (𝑛)]. We now verify that 𝑖 ★ is the largest index passing the noisy margin test. e𝑆 (1) = 1 > 2/𝑓 (𝑛). If 𝑖 ★ ≥ 2, then for every Part 1: 𝑖 ★ passes the noisy margin test. If 𝑖 ★ = 1, then 𝑀 ★ 𝑗 < 𝑖 , using (D.9) on both indices, ef rr𝑆 (𝐿 𝑗 ) − ef rr𝑆 (𝐿𝑖★ ) ≥ err D (𝐿 𝑗 ) − 2𝑓 1(𝑛) − err D (𝐿𝑖★ ) + 2𝑓 1(𝑛) 1 = (err D (𝐿 𝑗 ) − err D (𝐿𝑖★ )) − 𝑓 (𝑛) 1 ≥ 𝑐 gap − . 𝑓 (𝑛) For 𝑛 ≥ 𝑛 0 we have 𝑐 gap > 3/𝑓 (𝑛), so 𝑐 gap − 1/𝑓 (𝑛) > 2/𝑓 (𝑛). Taking the minimum over 𝑗 < 𝑖 ★ gives e𝑆 (𝑖 ★) > 2/𝑓 (𝑛). 𝑀 Part 2: No 𝑖 > 𝑖 ★ passes the noisy margin test. Fix 𝑖 > 𝑖 ★. By the optimality of 𝑖 ★, err D (𝐿𝑖 ) ≥ err D (𝐿𝑖★ ). Using (D.9), ef rr𝑆 (𝐿𝑖★ ) − ef rr𝑆 (𝐿𝑖 ) ≤ err D (𝐿𝑖★ ) + 2𝑓 1(𝑛) − err D (𝐿𝑖 ) − 2𝑓 1(𝑛) 1 = (err D (𝐿𝑖★ ) − err D (𝐿𝑖 )) + 𝑓 (𝑛) 1 ≤ . 𝑓 (𝑛) e𝑆 (𝑖), we have 𝑀 e𝑆 (𝑖) ≤ 1/𝑓 (𝑛) < 2/𝑓 (𝑛), Since 𝑗 = 𝑖 ★ is among the candidates in the minimum defining 𝑀 so 𝑖 fails the noisy margin test. Since 𝑖 ★ passes and no 𝑖 > 𝑖 ★ passes, the algorithm outputs b 𝑖 = 𝑖 ★. □ D.2.3

Putting Things Together

Theorem D.14 (Guarantees of Algorithm 2). Let C = {𝐿𝑖 }𝑖 ∈ℕ be a countable collection of languages and let D be any distribution over U. Suppose Assumption D.1 holds. Let 𝜀 > 0, 𝛿 ∈ (0, 1), and let 𝑓 : ℕ → ℕ satisfy 𝑓 (𝑛) → ∞. Then for all sufficiently large 𝑛, Algorithm 2 has the following guarantees: • Privacy. Algorithm 2 is (𝜀, 𝛿)-differentially private. • Utility. The identification error satisfies id IdErr(A𝜀,𝛿,𝑓 , D, C, 𝑛) ≤ 2𝑓 (𝑛) exp −

𝑛 𝜀 2𝑛 2 + 2𝑓 (𝑛) exp − . 8𝑓 (𝑛) 2 64𝑓 (𝑛) 3 log(1.25/𝛿)

(D.10)

Proof. Privacy. This directly follows from Lemma D.11. Utility. By Lemma D.13, b 𝑖 = 𝑖 ★ whenever E ∩ F holds. Therefore id IdErr(A𝜀,𝛿,𝑓 , D, C, 𝑛) ≤ Pr [b 𝑖 ≠ 𝑖 ★] ≤ Pr[E𝑐 ] + Pr[F 𝑐 ]. 𝑆,𝑟

Applying Lemma D.4 and Lemma D.12: id IdErr(A𝜀,𝛿,𝑓 , D, C, 𝑛) ≤ 2𝑓 (𝑛) exp −

𝑛 𝜀 2𝑛 2 + 2𝑓 (𝑛) exp − . 8𝑓 (𝑛) 2 64𝑓 (𝑛) 3 log(1.25/𝛿) □ 26

Remark D.15 (Comparison with Pure DP and Interpretation). The approximate DP analysis is structurally simpler: once both concentration events hold, correctness is deterministic (no exponential mechanism). The cost is that the noise event F depends on 𝜀, 𝛿, and 𝑓 (𝑛) jointly. The bound (D.10) decomposes into a statistical term 2𝑓 (𝑛) exp(−𝑛/(8𝑓 (𝑛) 2 )), identical to the pure DP case, and a privacy term scaling as exp(−𝜀 2𝑛 2 /𝑓 (𝑛) 3 ) rather than exp(−𝜀𝑛/𝑓 (𝑛) 2 ), reflecting the different noise mechanism. The optimal tradeoff is analyzed in Corollary D.16. Corollary D.16 (Explicit Rates for Approximate DP). Substituting specific horizons into (D.10): • 𝑓 (𝑛) = 𝑛𝛼 for 𝛼 ∈ (0, 1/2): 𝜀 2𝑛 2−3𝛼 id , D, C, 𝑛) ≲ exp −𝑛 1−2𝛼 + exp − . IdErr(A𝜀,𝛿,𝑓 log(1/𝛿) Since 2 − 3𝛼 > 1 − 2𝛼 for all 𝛼 ∈ (0, 1), the statistical term dominates whenever 𝜀 = Ω(1) and 𝛿 is at most polynomially small. √︁ • 𝑓 (𝑛) = 𝑐 log 𝑛 for sufficiently large 𝑐 > 0: 𝑛 𝜀 2𝑛 2 id + exp − 3/2 IdErr(A𝜀,𝛿,𝑓 , D, C, 𝑛) ≲ exp − log 𝑛 log 𝑛 · log(1/𝛿) for any constant 𝜀 > 0 and 𝛿 ≥ exp(−poly(𝑛)). √︁ • 𝜀 = 𝑛 −𝛾 for 𝛾 > 0 with 𝑓 (𝑛) = 𝑐 log 𝑛: 𝑛 𝑛 2−2𝛾 id IdErr(A𝜀,𝛿,𝑓 , D, C, 𝑛) ≲ exp − + exp − 3/2 . log 𝑛 log 𝑛 · log(1/𝛿) The privacy term dominates when 𝛾 > 1/2.

Proofs for Section 4 (Upper Bounds for DP Generation)

We fix an enumeration of the universe U = {𝑢𝑖 }𝑖 ∈ℕ and assume that every language 𝐿 ∈ C is infinite. For a dataset 𝑆 = (𝑥 1, . . . , 𝑥𝑛 ) ∈ U𝑛 and 𝑥 ∈ U, we define the multiplicity 𝑁𝑆 (𝑥) :=

𝑛 ∑︁

1{𝑥𝑡 = 𝑥 }.

𝑡 =1

Definition E.1 (Witness Index 𝑖 (C, D)). Given a collection C of languages and a distribution D over U = {𝑢𝑖 }𝑖 ∈ℕ , the witness index is 𝑖 (C, D) := min 𝑖 ∈ ℕ : ∀ 𝐿 ∈ C with 𝐿 ⊈ supp(D), ∃ 𝑘 ≤ 𝑖 s.t. 𝑢𝑘 ∈ 𝐿 \ supp(D) , with the convention min ∅ = ∞. In words, 𝑖 (C, D) is the smallest index such that every language not fully contained in supp(D) has a witness — a string in the language but outside the support — appearing within the first 𝑖 (C, D) elements of U. For any finite collection C, we always have 𝑖 (C, D) < ∞. We work under the following two assumptions throughout this section. Assumption E.2 (Finite witness index). The witness index is finite, i.e., 𝑖 (C, D) < ∞. Assumption E.3 (Support contains a reference language). There exists an index 𝑖 ★ ∈ ℕ such that 𝐿𝑖★ ⊆ supp(D). Let 𝑖 ★ denote the smallest such index. 27

E.1

Proof of Theorem 4.5 (Pure DP Generation with a Public Witness Bound)

We first consider the setting where a public upper bound on the witness index is available. Assumption E.4 (Public Witness Bound). There is a public integer 𝑊 ≥ 𝑖 (C, D). Here “public” means that 𝑊 is auxiliary input given to the algorithm before observing the private sample 𝑆 ∼ D 𝑛 ; it is not part of the data protected by differential privacy. E.1.1

Setup and Notations

For each language 𝐿𝑖 and the witness window [𝑊 ], define 𝐼𝑖 (𝑊 ) := {𝑘 ∈ [𝑊 ] : 𝑢𝑘 ∈ 𝐿𝑖 }

(E.1)

to be the set of indices of strings in 𝐿𝑖 within the witness window. Define the minimum prefix count ( min𝑘 ∈𝐼𝑖 (𝑊 ) 𝑁𝑆 (𝑢𝑘 ), if 𝐼𝑖 (𝑊 ) ≠ ∅, 𝑎𝑊 (E.2) 𝑖 (𝑆) := 𝑛, if 𝐼𝑖 (𝑊 ) = ∅, the deficit 𝑑𝑖𝑊 (𝑆) := 𝑔(𝑛) − 𝑎𝑊 𝑖 (𝑆) +,

(E.3)

𝑞𝑊 (𝑆, 𝑖) := −𝑑𝑖𝑊 (𝑆).

(E.4)

and the score

Here 𝑔 : ℕ → ℕ is a count threshold satisfying 𝑔(𝑛) → ∞; its role is analogous to the margin 2/𝑓 (𝑛) in identification. The score is at most 0 (achieved when the prefix is well-covered) and equals −𝑔(𝑛) when a witness string is never observed. We also define the following quantities associated with the reference language 𝐿𝑖★ : ★ 𝐼𝑊 := 𝐼𝑖★ (𝑊 ) = {𝑘 ∈ [𝑊 ] : 𝑢𝑘 ∈ 𝐿𝑖★ },

★ 𝑝𝑊 := min Pr [𝑥 = 𝑢𝑘 ]. ★ 𝑘 ∈𝐼𝑊 𝑥∼D

(E.5)

★ has positive probability under D, so 𝑝 ★ > 0. Since 𝐿𝑖★ ⊆ supp(D), every string 𝑢𝑘 with 𝑘 ∈ 𝐼𝑊 𝑊

E.1.2

Privacy Analysis

Lemma E.5 (Sensitivity of 𝑞𝑊 ). The score function 𝑞𝑊 defined in (E.4) has sensitivity 1. Proof. Fix 𝑖 ∈ [𝑓 (𝑛)] and let 𝑆, 𝑆 ′ ∈ U𝑛 be neighboring datasets. For every 𝑥 ∈ U, the multiplicity satisfies |𝑁𝑆 (𝑥) − 𝑁𝑆 ′ (𝑥)| ≤ 1. If 𝐼𝑖 (𝑊 ) ≠ ∅, then 𝑎𝑊 𝑖 (𝑆) = min𝑘 ∈𝐼𝑖 (𝑊 ) 𝑁𝑆 (𝑢𝑘 ). Since each 𝑁𝑆 (𝑢𝑘 ) changes by at most 1 and the minimum of functions preserves Lipschitz constants, 𝑊 ′ |𝑎𝑊 𝑖 (𝑆) − 𝑎𝑖 (𝑆 )| ≤ 1. 𝑊 ′ If 𝐼𝑖 (𝑊 ) = ∅, then 𝑎𝑊 𝑖 (𝑆) = 𝑎𝑖 (𝑆 ) = 𝑛 and the bound holds trivially. The map 𝑥 ↦→ (𝑔(𝑛) − 𝑥)+ is 1-Lipschitz, so |𝑑𝑖𝑊 (𝑆) − 𝑑𝑖𝑊 (𝑆 ′ )| ≤ 1. Therefore

|𝑞𝑊 (𝑆, 𝑖) − 𝑞𝑊 (𝑆 ′, 𝑖)| = |𝑑𝑖𝑊 (𝑆) − 𝑑𝑖𝑊 (𝑆 ′ )| ≤ 1. □ 28

Remark E.6 (Comparison with Identification). The generation score has constant sensitivity 1 (integer multiplicity counts), whereas the identification score has sensitivity Θ(𝑓 (𝑛) 2 /𝑛) (empirical error averages amplified by the 𝑓 (𝑛) 2 coefficient). Moreover, the score separation is structurally simpler: there is no case analysis for 𝑖 < 𝑖 ★ vs. 𝑖 > 𝑖 ★, since the witness test treats all bad languages uniformly, and the score gap is 𝑔(𝑛) rather than 1. Together, these give a qualitatively smaller price of privacy: the non-private rate exp(−Θ(𝑛)) of Høgsgaard and Pabbaraju [2026] is matched when 𝜀 = Ω(1), and the only cost is the factor of 𝜀 in the exponent when 𝜀 < 1, compared with identification where 𝑟 (𝑛) = 𝑜 (𝑛) rather than Θ(𝑛). Lemma E.7 (Privacy). Algorithm 3 is 𝜀-differentially private. Proof. The language selection on line 7 applies the exponential mechanism with score 𝑞𝑊 over range [𝑓 (𝑛)]. By Lemma E.5, 𝑞𝑊 has sensitivity Δ = 1, so this step is 𝜀-DP. The subsequent output step (lines 12–13) is a deterministic function of the private output b 𝑖 and public randomness b 𝑗 , and is therefore 𝜀-DP by post-processing (Lemma 2.3). □ E.1.3

Utility Analysis

The utility analysis proceeds in three steps: (i) a coverage event E𝑊 under which every relevant string of 𝐿𝑖★ in the witness window appears at least 𝑔(𝑛) times (Lemma E.8); (ii) on E𝑊 , the good language 𝐿𝑖★ has score 0 while every bad language has score −𝑔(𝑛), creating a score gap of 𝑔(𝑛) (Lemma E.9); (iii) the exponential mechanism exploits this gap to select a good language, and the output step produces a novel string from its support (Lemma E.10). Lemma E.8 (Coverage of the Good Prefix). Define the event ★ . E𝑊 := 𝑁𝑆 (𝑢𝑘 ) ≥ 𝑔(𝑛) ∀ 𝑘 ∈ 𝐼𝑊 ★ /2 for all large enough 𝑛, then If 𝑔(𝑛) ≤ 𝑛𝑝𝑊

𝑛𝑝 ★ 𝑐 ★ Pr 𝑛 [E𝑊 ] ≤ |𝐼𝑊 | exp − 𝑊 . 𝑆∼D 8 ★ and let 𝑝 := Pr ★ Proof. Fix 𝑘 ∈ 𝐼𝑊 𝑥∼D [𝑥 = 𝑢𝑘 ], so that 𝑝𝑘 ≥ 𝑝𝑊 > 0. The multiplicity 𝑁𝑆 (𝑢𝑘 ) = 𝑘 Í𝑛 𝑡 =1 1{𝑥𝑡 = 𝑢𝑘 } is a sum of 𝑛 independent Bernoulli(𝑝𝑘 ) random variables with mean 𝜇𝑘 = 𝑛𝑝𝑘 . Since ★ /2 ≤ 𝑛𝑝 /2 = 𝜇 /2, the event {𝑁 (𝑢 ) < 𝑔(𝑛)} is contained in {𝑁 (𝑢 ) ≤ 𝜇 /2}. By the 𝑔(𝑛) ≤ 𝑛𝑝𝑊 𝑆 𝑘 𝑆 𝑘 𝑘 𝑘 𝑘 Chernoff bound (Lemma B.2) with 𝑡 = 1/2,

𝜇 𝑛𝑝 ★ 𝑘 Pr 𝑁𝑆 (𝑢𝑘 ) ≤ 𝜇𝑘 /2 ≤ exp − ≤ exp − 𝑊 . 8 8 ★ yields A union bound over 𝑘 ∈ 𝐼𝑊

𝑐 Pr[E𝑊 ]≤

𝑛𝑝 ★ 𝑛𝑝 ★ ★ exp − 𝑊 = |𝐼𝑊 | exp − 𝑊 . 8 8 ★

∑︁

𝑘 ∈𝐼𝑊

□ Lemma E.9 (Score separation on E𝑊 ). On the event E𝑊 : (a) 𝑞𝑊 (𝑆, 𝑖 ★) = 0. (b) 𝑞𝑊 (𝑆, 𝑖) = −𝑔(𝑛) for every 𝑖 ∈ [𝑓 (𝑛)] such that 𝐿𝑖 ⊈ supp(D). 29

Consequently, OPT𝑞𝑊 (𝑆) = 0 and every bad language has a score gap of exactly 𝑔(𝑛). ★ satisfies 𝑁 (𝑢 ) ≥ 𝑔(𝑛). Proof. Part (a): The good language achieves score 0. On E𝑊 , every 𝑘 ∈ 𝐼𝑊 𝑆 𝑘 𝑊 𝑊 𝑊 ★ ★ = ∅ (i.e., If 𝐼𝑊 ≠ ∅, then 𝑎𝑖★ (𝑆) = min𝑘 ∈𝐼𝑊★ 𝑁𝑆 (𝑢𝑘 ) ≥ 𝑔(𝑛), so 𝑑𝑖★ (𝑆) = (𝑔(𝑛) − 𝑎𝑖★ (𝑆))+ = 0. If 𝐼𝑊 𝐿𝑖★ has no string with index ≤ 𝑊 ), then 𝑎𝑊 (𝑆) = 𝑛 ≥ 𝑔(𝑛), so 𝑑𝑖𝑊★ (𝑆) = 0 as well. In either case, 𝑖★ 𝑞𝑊 (𝑆, 𝑖 ★) = −𝑑𝑖𝑊★ (𝑆) = 0.

Part (b): Every bad language achieves score −𝑔(𝑛). Fix 𝑖 ∈ [𝑓 (𝑛)] with 𝐿𝑖 ⊈ supp(D). Since 𝑊 ≥ 𝑖 (C, D) (Assumption E.4), by Definition E.1 there exists 𝑘 ≤ 𝑊 such that 𝑢𝑘 ∈ 𝐿𝑖 \ supp(D). In particular, 𝑘 ∈ 𝐼𝑖 (𝑊 ) (so 𝐼𝑖 (𝑊 ) ≠ ∅) and 𝑢𝑘 ∉ supp(D), meaning 𝑢𝑘 can never appear in any sample from 𝑊 D. Therefore 𝑁𝑆 (𝑢𝑘 ) = 0, which gives 𝑎𝑊 𝑖 (𝑆) ≤ 𝑁𝑆 (𝑢𝑘 ) = 0. Hence 𝑑𝑖 (𝑆) = (𝑔(𝑛) − 0)+ = 𝑔(𝑛) and 𝑞𝑊 (𝑆, 𝑖) = −𝑔(𝑛). □ Lemma E.10 (Private Selection and Output). Define 𝜀𝑔(𝑛) 𝛽 sel := 𝑓 (𝑛) exp − , 4

𝑛 𝛽 out := exp − . 2

If 𝛽 sel < 1, then on the event E𝑊 : (a) The exponential mechanism selects a good language (i.e., 𝐿b𝑖 ⊆ supp(D)) with probability at least 1 − 𝛽 sel . (b) Conditioned on 𝐿b𝑖 ⊆ supp(D), the output 𝑥b satisfies 𝑥b ∈ supp(D) \ 𝑆 with probability at least 1 − 𝛽 out . Proof. Part (a): Language selection. On E𝑊 , Lemma E.9 gives OPT𝑞𝑊 (𝑆) = 0 and 𝑞𝑊 (𝑆, 𝑖) = −𝑔(𝑛) for every 𝑖 with 𝐿𝑖 ⊈ supp(D). By the utility guarantee of the exponential mechanism (Lemma 2.4) with 𝑖 satisfies sensitivity Δ = 1 (Lemma E.5) and range |R| = 𝑓 (𝑛), with probability at least 1 − 𝛽 sel the output b 𝑞𝑊 (𝑆, b 𝑖 ) ≥ OPT𝑞𝑊 (𝑆) −

2 𝑓 (𝑛) ln . 𝜀 𝛽 sel

Substituting 𝛽 sel = 𝑓 (𝑛) exp(−𝜀𝑔(𝑛)/4): ln and therefore

𝑓 (𝑛) 𝜀𝑔(𝑛) = , 𝛽 sel 4

2 𝑓 (𝑛) 2 𝜀𝑔(𝑛) 𝑔(𝑛) ln = · = . 𝜀 𝛽 sel 𝜀 4 2

This gives 𝑞𝑊 (𝑆, b 𝑖 ) ≥ 0 − 𝑔(𝑛)/2 = −𝑔(𝑛)/2. Since every bad language has score −𝑔(𝑛) < −𝑔(𝑛)/2, the selected language 𝐿b𝑖 must satisfy 𝐿b𝑖 ⊆ supp(D). Part (b): Output novelty. Suppose 𝐿b𝑖 ⊆ supp(D). The algorithm outputs the b 𝑗 -th smallest-indexed string from the set 𝑇b𝑖 := 𝐿b𝑖 ∩ {𝑢𝑊 +1, 𝑢𝑊 +2, . . .}, where b 𝑗 ∼ Unif ( [2𝑛 ]). Since 𝐿b𝑖 is infinite, 𝑇b𝑖 is infinite and in particular |𝑇b𝑖 | ≥ 2𝑛 . Moreover, since 𝐿b𝑖 ⊆ supp(D), every string in 𝑇b𝑖 belongs to supp(D). The sample 𝑆 has size 𝑛, so at most 𝑛 strings from 𝑇b𝑖 can appear in 𝑆. Since b 𝑗 is uniform over [2𝑛 ] and independent of 𝑆 (it is public randomness), 𝑛 𝑛 Pr[b 𝑥 ∈ 𝑆 | 𝐿b𝑖 ⊆ supp(D)] ≤ 𝑛 ≤ exp − 2 2 𝑛 for all 𝑛 ≥ 15, where the last inequality uses 𝑛/2 ≤ exp(−𝑛/2). □

E.1.4

Putting Things Together

Theorem E.11 (Guarantees of Algorithm 3, Restatement of Theorem 4.6). Let C = {𝐿𝑖 }𝑖 ∈ℕ be a countable collection of infinite languages and let D be any distribution over U. Suppose Assumptions E.2, E.3, and E.4 ★ /2 for all large enough 𝑛. hold. Let 𝜀 > 0, and let 𝑓 , 𝑔 : ℕ → ℕ satisfy 𝑓 (𝑛) → ∞, 𝑔(𝑛) → ∞, and 𝑔(𝑛) ≤ 𝑛𝑝𝑊 Suppose further that 𝑓 (𝑛) ≥ 𝑖 ★. Then for all sufficiently large 𝑛, Algorithm 3 has the following guarantees: • Privacy. Algorithm 3 is 𝜀-differentially private. • Utility. The generation error satisfies 𝑛𝑝 ★ 𝑛 𝜀𝑔(𝑛) gen ★ + exp − . GenErr(A𝜀,𝑓 ,𝑔,𝑊 , D, C, 𝑛) ≤ |𝐼𝑊 | exp − 𝑊 + 𝑓 (𝑛) exp − 8 4 2 {z } | {z } | {z } | coverage

privacy

(E.6)

collison

Proof. Privacy. This directly follows from Lemma E.7. Utility. The generation fails (i.e., 𝑥b ∉ supp(D) \ 𝑆) only if at least one of the following three bad events occurs: (i) The coverage event E𝑊 fails: the good prefix of 𝐿𝑖★ is not well-covered. (ii) The exponential mechanism selects a bad language: 𝐿b𝑖 ⊈ supp(D). (iii) The selected language is good but the output string is already in 𝑆: 𝑥b ∈ 𝑆. By a union bound, gen

𝑐 GenErr(A𝜀,𝑓 ,𝑔,𝑊 , D, C, 𝑛) ≤ Pr[E𝑊 ] + Pr[𝐿b𝑖 ⊈ supp(D) | E𝑊 ] + Pr[b 𝑥 ∈ 𝑆 | 𝐿b𝑖 ⊆ supp(D)].

Applying Lemma E.8 (term (i)), Lemma E.10(a) (term (ii)), and Lemma E.10(b) (term (iii)): 𝜀𝑔(𝑛) 𝑛 𝑛𝑝 ★ gen ★ + exp − . GenErr(A𝜀,𝑓 ,𝑔,𝑊 , D, C, 𝑛) ≤ |𝐼𝑊 | exp − 𝑊 + 𝑓 (𝑛) exp − 8 4 2 □ Remark E.12 (Interpretation of the bound). The bound (E.6) consists of three terms: a coverage term ★ | exp(−𝑛𝑝 ★ /8), present even without privacy, controlling under-representation of 𝐿 ★ strings in the witness |𝐼𝑊 𝑖 𝑊 window; a privacy term 𝑓 (𝑛) exp(−𝜀𝑔(𝑛)/4), controlling the exponential mechanism’s failure to select a good language (with direct 𝜀-dependence thanks to constant sensitivity); and a negligible collision term exp(−𝑛/2). The no-public-bound case (E.12) has the same structure, but the coverage term now depends on ℎ(𝑛) through 𝐼ℎ★ and 𝑝ℎ★, and the privacy term acquires an extra ℎ(𝑛) prefactor from the enlarged search space [𝑓 (𝑛)] × [ℎ(𝑛)]. Corollary E.13 (Exponential rate with known mass floor). Under the conditions of Theorem E.11, suppose ★ . Setting 𝑔(𝑛) = ⌊𝑛𝑝 /2⌋ and additionally that the learner is given a constant 𝑝 0 > 0 such that 𝑝 0 ≤ 𝑝𝑊 0 ★ choosing any 𝑓 with 𝑓 (𝑛) ≥ 𝑖 and log 𝑓 (𝑛) = 𝑜 (𝑛), the generation error satisfies 𝑛𝑝 ★ 𝜀𝑛𝑝 𝑛 0 gen ★ GenErr(A𝜀,𝑓 ,𝑔,𝑊 , D, C, 𝑛) ≤ |𝐼𝑊 | exp − 𝑊 + 𝑓 (𝑛) exp − + exp − 8 8 2 ≲ exp(− min{1, 𝜀} · 𝑛). In particular, for constant 𝜀 > 0, the rate is exp(−Ω(𝑛)).

★ , we have 𝑔(𝑛) = ⌊𝑛𝑝 /2⌋ ≤ 𝑛𝑝 ★ /2, so the condition of Theorem E.11 is satisfied. Proof. Since 𝑝 0 ≤ 𝑝𝑊 0 𝑊 Substituting 𝑔(𝑛) ≥ 𝑛𝑝 0 /2 − 1 ≥ 𝑛𝑝 0 /4 (for large 𝑛) into (E.6):

𝜀𝑛𝑝 𝜀𝑔(𝑛) 0 ≤ 𝑓 (𝑛) exp − . 𝑓 (𝑛) exp − 4 16 ★ | exp(−𝑛𝑝 ★ /8) Since log 𝑓 (𝑛) = 𝑜 (𝑛), the factor 𝑓 (𝑛) is absorbed into the exponential. The coverage term |𝐼𝑊 𝑊 ★ ★ is exp(−Ω(𝑛)) since |𝐼𝑊 | and 𝑝𝑊 are positive constants. The collision term exp(−𝑛/2) is exp(−Ω(𝑛)). Taking the maximum, all three terms are exp(−Ω(min{1, 𝜀} · 𝑛)). □

E.2

Proof of Theorem 4.6 (Pure DP Generation without a Public Witness Bound)

We now remove the assumption that a public upper bound on the witness index is available. The main challenge is that the witness window 𝑖 (C, D) is unknown and depends on the private data through D. Our approach is to jointly search over both the language index 𝑖 and a candidate witness threshold 𝑡, using a score that rewards large thresholds (indicating progress past the witness window) while penalizing languages that fail the witness test at threshold 𝑡. E.2.1

Setup and Notation

Let 𝑓 , 𝑔, ℎ : ℕ → ℕ be functions satisfying 𝑓 (𝑛) → ∞, 𝑔(𝑛) → ∞, and ℎ(𝑛) → ∞. The parameter 𝑓 (𝑛) controls the language horizon, 𝑔(𝑛) is the count threshold (as in the public-bound setting), and ℎ(𝑛) is the threshold horizon that upper bounds the witness index for large enough 𝑛. For each language 𝐿𝑖 and candidate threshold 𝑡 ∈ [ℎ(𝑛)], define 𝐼𝑖 (𝑡) := {𝑘 ∈ [𝑡] : 𝑢𝑘 ∈ 𝐿𝑖 }.

(E.7)

For each 𝑆 ∈ U𝑛 and each pair (𝑖, 𝑡) ∈ [𝑓 (𝑛)] × [ℎ(𝑛)], we define the minimum prefix count ( min𝑘 ∈𝐼𝑖 (𝑡 ) 𝑁𝑆 (𝑢𝑘 ), if 𝐼𝑖 (𝑡) ≠ ∅, 𝑎𝑖,𝑡 (𝑆) := 𝑛, if 𝐼𝑖 (𝑡) = ∅,

(E.8)

the deficit 𝑑𝑖,𝑡 (𝑆) := 𝑔(𝑛) − 𝑎𝑖,𝑡 (𝑆) +,

(E.9)

and the score 𝑞 pair (𝑆, (𝑖, 𝑡)) := 𝑡 −

ℎ(𝑛) 𝑑𝑖,𝑡 (𝑆). 𝑔(𝑛)

(E.10)

(𝑛) The term 𝑡 rewards larger thresholds, while the penalty ℎ𝑔 (𝑛) 𝑑𝑖,𝑡 (𝑆) suppresses pairs where the language fails the witness test at threshold 𝑡. The coefficient ℎ(𝑛)/𝑔(𝑛) is chosen so that a bad language with full deficit 𝑔(𝑛) incurs a penalty of exactly ℎ(𝑛), ensuring its score is at most 𝑡 − ℎ(𝑛) ≤ 0. We also define quantities associated with the reference language 𝐿𝑖★ at the threshold horizon:

𝐼ℎ★ := 𝐼𝑖★ (ℎ(𝑛)) = {𝑘 ∈ [ℎ(𝑛)] : 𝑢𝑘 ∈ 𝐿𝑖★ },

𝑝ℎ★ := min★ Pr [𝑥 = 𝑢𝑘 ]. 𝑘 ∈𝐼ℎ 𝑥∼D

(E.11)

Since 𝐿𝑖★ ⊆ supp(D), every string 𝑢𝑘 with 𝑘 ∈ 𝐼ℎ★ has positive probability under D, so 𝑝ℎ★ > 0. Note that 𝑝ℎ★ depends on ℎ(𝑛) and may decrease as ℎ(𝑛) grows, since the minimum is taken over a larger set. This 32

gen

Algorithm 6 Pure DP Generation without a Public Witness Bound A𝜀,𝑓 ,𝑔,ℎ Require: Dataset 𝑆 = (𝑥 1, . . . , 𝑥𝑛 ) ∈ U 𝑛 , privacy parameter 𝜀 > 0, functions 𝑓 , 𝑔, ℎ : ℕ → ℕ, language collection C = {𝐿𝑖 }𝑖 ∈ℕ . Ensure: A string 𝑥b ∈ U. 1: for 𝑘 ∈ [ℎ(𝑛)] do Í 2: 𝑁𝑆 (𝑢𝑘 ) ← 𝑛𝑡=1 1{𝑥𝑡 = 𝑢𝑘 } 3: end for 4: for 𝑖 ∈ [𝑓 (𝑛)], 𝑡 ∈ [ℎ(𝑛)] do 5: Compute 𝐼𝑖 (𝑡), 𝑎𝑖,𝑡 (𝑆), 𝑑𝑖,𝑡 (𝑆), 𝑞 pair (𝑆, (𝑖, 𝑡)) via (E.7)–(E.10) 6: end for 7: Sample b 𝑖, b 𝑡 ∼ EM𝜀 𝑆, 𝑞 pair, [𝑓 (𝑛)] × [ℎ(𝑛)] ⊲ Privately select a (language, threshold) pair 8: Sample b 𝑗 ∼ Unif ( [2𝑛 ]) ⊲ Public randomness 9: return the b 𝑗 -th smallest-indexed string in 𝐿b𝑖 ∩ {𝑢b𝑡 +1, 𝑢b𝑡 +2, . . .} creates a tension: larger ℎ(𝑛) provides a wider search range but requires a smaller 𝑔(𝑛) for coverage, which in turn weakens the score gap exploited by the exponential mechanism. Compared to Algorithm 3, the key difference is that the exponential mechanism now searches over pairs (𝑖, 𝑡) rather than language indices 𝑖 alone. The selected threshold b 𝑡 replaces the role of the public 𝑖 and b witness bound 𝑊 : the output string is drawn from the selected language beyond index b 𝑡 . Since both b 𝑡 are part of the exponential mechanism’s output, the subsequent output step (lines 7–8) is post-processing and incurs no additional privacy cost. E.2.2

Privacy Analysis

Lemma E.14 (Sensitivity of the pair score). The score function 𝑞 pair defined in (E.10) has sensitivity ℎ(𝑛)/𝑔(𝑛). Proof. Fix (𝑖, 𝑡) ∈ [𝑓 (𝑛)] × [ℎ(𝑛)] and let 𝑆, 𝑆 ′ ∈ U 𝑛 be neighboring datasets. By the same argument as in Lemma E.5, the minimum prefix count satisfies |𝑎𝑖,𝑡 (𝑆) − 𝑎𝑖,𝑡 (𝑆 ′ )| ≤ 1 (since each multiplicity changes by at most 1, and the minimum preserves Lipschitz constants; or 𝑎𝑖,𝑡 (𝑆) = 𝑎𝑖,𝑡 (𝑆 ′ ) = 𝑛 when 𝐼𝑖 (𝑡) = ∅). Since 𝑥 ↦→ (𝑔(𝑛) − 𝑥)+ is 1-Lipschitz, |𝑑𝑖,𝑡 (𝑆) − 𝑑𝑖,𝑡 (𝑆 ′ )| ≤ 1. Therefore |𝑞 pair (𝑆, (𝑖, 𝑡)) − 𝑞 pair (𝑆 ′, (𝑖, 𝑡))| =

ℎ(𝑛) ℎ(𝑛) |𝑑𝑖,𝑡 (𝑆) − 𝑑𝑖,𝑡 (𝑆 ′ )| ≤ . 𝑔(𝑛) 𝑔(𝑛) □

Remark E.15 (Sensitivity and Ccore gap without a Public Bound). The pair score has sensitivity ℎ(𝑛)/𝑔(𝑛), lying between the constant sensitivity 1 of the public-bound case (Lemma E.5) and the 2𝑓 (𝑛) 2 /𝑛 of identification (Lemma D.2). The increase from 1 to ℎ(𝑛)/𝑔(𝑛) is the cost of not knowing the witness bound. Meanwhile, the score gap grows to ℎ(𝑛) − 𝑖 (C, D) + 1 = Ω(ℎ(𝑛)), so the effective ratio (gap/sensitivity) is approximately 𝑔(𝑛)(1 − 𝑖 (C, D)/ℎ(𝑛)) ≈ 𝑔(𝑛) for large ℎ(𝑛), comparable to the public-bound case. Lemma E.16 (Privacy). Algorithm 6 is 𝜀-differentially private. Proof. The pair selection on line 6 applies the exponential mechanism with score 𝑞 pair over the finite range [𝑓 (𝑛)] × [ℎ(𝑛)]. By Lemma E.14, 𝑞 pair has sensitivity Δ = ℎ(𝑛)/𝑔(𝑛), so this step is 𝜀-DP. The output step (lines 7–8) is a deterministic function of the private output (b 𝑖, b 𝑡 ) and public randomness b 𝑗 , and is therefore 𝜀-DP by post-processing (Lemma 2.3). □

E.2.3

Utility Analysis

The utility analysis proceeds in three steps, paralleling the public-bound case: (i) a coverage event Eℎ under which every relevant string of 𝐿𝑖★ up to index ℎ(𝑛) appears at least 𝑔(𝑛) times (Lemma E.17); (ii) on Eℎ , the good pair (𝑖 ★, ℎ(𝑛)) achieves the maximum score while every bad pair has a much lower score (Lemma E.18); (iii) the exponential mechanism exploits this gap to select a good language (Lemma E.19). Lemma E.17 (Coverage of the Good Prefix). Define the event Eℎ := 𝑁𝑆 (𝑢𝑘 ) ≥ 𝑔(𝑛) ∀ 𝑘 ∈ 𝐼ℎ★ . If 𝑔(𝑛) ≤ 𝑛𝑝ℎ★/2 for all large enough 𝑛, then 𝑛𝑝 ★ Pr 𝑛 [Eℎ𝑐 ] ≤ |𝐼ℎ★ | exp − ℎ . 𝑆∼D 8 ★ replaced by 𝑝 ★. Proof. The proof is identical to that of Lemma E.8, with 𝑊 replaced by ℎ(𝑛) and 𝑝𝑊 ℎ

□

Lemma E.18 (Score Separation on Eℎ ). Suppose ℎ(𝑛) ≥ 𝑖 (C, D). On the event Eℎ : (a) 𝑞 pair (𝑆, (𝑖 ★, ℎ(𝑛))) = ℎ(𝑛). (b) For every (𝑖, 𝑡) ∈ [𝑓 (𝑛)] × [ℎ(𝑛)] with 𝐿𝑖 ⊈ supp(D): 𝑞 pair (𝑆, (𝑖, 𝑡)) ≤ 𝑖 (C, D) − 1. Consequently, OPT𝑞pair (𝑆) = ℎ(𝑛) and every bad pair has a score gap of at least ℎ(𝑛) − 𝑖 (C, D) + 1. Proof. Assume Eℎ holds throughout. Part (a): The good pair achieves score ℎ(𝑛). On Eℎ , every 𝑘 ∈ 𝐼ℎ★ satisfies 𝑁𝑆 (𝑢𝑘 ) ≥ 𝑔(𝑛). If 𝐼𝑖★ (ℎ(𝑛)) ≠ ∅, then 𝑎𝑖★,ℎ (𝑛) (𝑆) = min𝑘 ∈𝐼𝑖★ (ℎ (𝑛) ) 𝑁𝑆 (𝑢𝑘 ) ≥ 𝑔(𝑛), so 𝑑𝑖★,ℎ (𝑛) (𝑆) = 0. If 𝐼𝑖★ (ℎ(𝑛)) = ∅, then 𝑎𝑖★,ℎ (𝑛) (𝑆) = 𝑛 ≥ 𝑔(𝑛), so 𝑑𝑖★,ℎ (𝑛) (𝑆) = 0 as well. In either case, 𝑞 pair (𝑆, (𝑖 ★, ℎ(𝑛))) = ℎ(𝑛) −

ℎ(𝑛) · 0 = ℎ(𝑛). 𝑔(𝑛)

Since 𝑞 pair (𝑆, (𝑖, 𝑡)) ≤ 𝑡 ≤ ℎ(𝑛) for all pairs (as the deficit is nonneg.), we have OPT𝑞pair (𝑆) = ℎ(𝑛). Part (b): Every bad pair has low score. Fix 𝑖 ∈ [𝑓 (𝑛)] with 𝐿𝑖 ⊈ supp(D) and any 𝑡 ∈ [ℎ(𝑛)]. We consider two cases depending on whether 𝑡 is large enough to contain a witness. Case 𝑡 ≥ 𝑖 (C, D): By Definition E.1, there exists 𝑘 ≤ 𝑖 (C, D) ≤ 𝑡 such that 𝑢𝑘 ∈ 𝐿𝑖 \ supp(D). In particular, 𝑘 ∈ 𝐼𝑖 (𝑡) and 𝑢𝑘 never appears in any sample from D, so 𝑁𝑆 (𝑢𝑘 ) = 0. Therefore 𝑎𝑖,𝑡 (𝑆) ≤ 𝑁𝑆 (𝑢𝑘 ) = 0, giving 𝑑𝑖,𝑡 (𝑆) = 𝑔(𝑛) and 𝑞 pair (𝑆, (𝑖, 𝑡)) = 𝑡 −

ℎ(𝑛) · 𝑔(𝑛) = 𝑡 − ℎ(𝑛) ≤ 0. 𝑔(𝑛)

Case 𝑡 < 𝑖 (C, D): Regardless of the deficit, the score satisfies 𝑞 pair (𝑆, (𝑖, 𝑡)) ≤ 𝑡 ≤ 𝑖 (C, D) − 1. Combining both cases, every bad pair has score at most max{0, 𝑖 (C, D) − 1} = 𝑖 (C, D) − 1 (since 𝑖 (C, D) ≥ 1). The score gap between the good pair and any bad pair is at least ℎ(𝑛) − (𝑖 (C, D) − 1) = ℎ(𝑛) − 𝑖 (C, D) + 1. □

Lemma E.19 (Private Selection and Output). Suppose ℎ(𝑛) ≥ 2 𝑖 (C, D) (so the score gap is at least ℎ(𝑛)/2). Define 𝑛 𝜀 𝑔(𝑛) , 𝛽 out := exp − . 𝛽 sel := 𝑓 (𝑛) ℎ(𝑛) exp − 8 2 If 𝛽 sel < 1, then on the event Eℎ : (a) The exponential mechanism selects a good language (i.e., 𝐿b𝑖 ⊆ supp(D)) with probability at least 1 − 𝛽 sel . (b) Conditioned on 𝐿b𝑖 ⊆ supp(D), the output 𝑥b satisfies 𝑥b ∈ supp(D) \ 𝑆 with probability at least 1 − 𝛽 out . Proof. Part (a): Pair selection. On Eℎ , Lemma E.18 gives OPT𝑞pair (𝑆) = ℎ(𝑛) and every bad pair (𝑖, 𝑡) (i.e., with 𝐿𝑖 ⊈ supp(D)) satisfies 𝑞 pair (𝑆, (𝑖, 𝑡)) ≤ 𝑖 (C, D) − 1 ≤ ℎ(𝑛)/2 − 1 < ℎ(𝑛)/2. By the utility guarantee of the exponential mechanism (Lemma 2.4) with sensitivity Δ = ℎ(𝑛)/𝑔(𝑛) (Lemma E.14) and range |R| = 𝑓 (𝑛) · ℎ(𝑛), with probability at least 1 − 𝛽 sel the output (b 𝑖, b 𝑡 ) satisfies 𝑞 pair (𝑆, (b 𝑖, b 𝑡 )) ≥ ℎ(𝑛) −

2ℎ(𝑛) 𝑓 (𝑛) ℎ(𝑛) . ln 𝑔(𝑛)𝜀 𝛽 sel

Substituting 𝛽 sel = 𝑓 (𝑛) ℎ(𝑛) exp(−𝜀 𝑔(𝑛)/8): ln and therefore

𝑓 (𝑛) ℎ(𝑛) 𝜀 𝑔(𝑛) = , 𝛽 sel 8

2ℎ(𝑛) 𝜀 𝑔(𝑛) ℎ(𝑛) · = . 𝑔(𝑛)𝜀 8 4

This gives 𝑞 pair (𝑆, (b 𝑖, b 𝑡 )) ≥ ℎ(𝑛)−ℎ(𝑛)/4 = 3ℎ(𝑛)/4. Since every bad pair has score at most ℎ(𝑛)/2 < 3ℎ(𝑛)/4, b b the selected pair (𝑖 , 𝑡 ) must satisfy 𝐿b𝑖 ⊆ supp(D). Part (b): Output novelty. Suppose 𝐿b𝑖 ⊆ supp(D). The algorithm outputs the b 𝑗 -th smallest-indexed string from 𝑇b𝑖,b𝑡 := 𝐿b𝑖 ∩ {𝑢b𝑡 +1, 𝑢b𝑡 +2, . . .}, where b 𝑗 ∼ Unif ( [2𝑛 ]). Since 𝐿b𝑖 is infinite, |𝑇b𝑖,b𝑡 | = ∞ ≥ 2𝑛 . Since 𝐿b𝑖 ⊆ supp(D), every string in 𝑇b𝑖,b𝑡 belongs to supp(D). At most 𝑛 strings from 𝑇b𝑖,b𝑡 can appear in 𝑆, so 𝑛 𝑛 Pr[b 𝑥 ∈ 𝑆 | 𝐿b𝑖 ⊆ supp(D)] ≤ 𝑛 ≤ exp − 2 2 for 𝑛 ≥ 15. E.2.4

□

Putting Things Together

Theorem E.20 (Guarantees of Algorithm 6, Restatement of Theorem 4.6). Let C = {𝐿𝑖 }𝑖 ∈ℕ be a countable collection of infinite languages and let D be any distribution over U. Suppose Assumptions E.2 and E.3 hold. Let 𝜀 > 0, and let 𝑓 , 𝑔, ℎ : ℕ → ℕ satisfy: (i) 𝑓 (𝑛) ≥ 𝑖 ★ and ℎ(𝑛) ≥ 2 𝑖 (C, D) for all large enough 𝑛; (ii) 𝑔(𝑛) → ∞ and 𝑔(𝑛) ≤ 𝑛𝑝ℎ★/2 for all large enough 𝑛. Then for all sufficiently large 𝑛, Algorithm 6 has the following guarantees: • Privacy. Algorithm 6 is 𝜀-differentially private. • Utility. The generation error satisfies 𝑛𝑝 ★ 𝜀 𝑔(𝑛) 𝑛 gen GenErr(A𝜀,𝑓 ,𝑔,ℎ , D, C, 𝑛) ≤ |𝐼ℎ★ | exp − ℎ + 𝑓 (𝑛) ℎ(𝑛) exp − + exp − . 8 8 2 35

(E.12)

Proof. Privacy. This directly follows from Lemma E.16. Utility. By a union bound over the three failure events: GenErr ≤ Pr[Eℎ𝑐 ] + Pr[𝐿b𝑖 ⊈ supp(D) | Eℎ ] + Pr[b 𝑥 ∈ 𝑆 | 𝐿b𝑖 ⊆ supp(D)]. Applying Lemma E.17 (coverage failure), Lemma E.19(a) (selection failure), and Lemma E.19(b) (collision): 𝜀 𝑔(𝑛) 𝑛 𝑛𝑝 ★ + exp − . GenErr ≤ |𝐼ℎ★ | exp − ℎ + 𝑓 (𝑛) ℎ(𝑛) exp − 8 8 2 □ Corollary E.21 (Rate with Known Mass Floor, Restatement of Corollary 4.7). Under the conditions of Theorem E.20, suppose additionally that the learner is given a constant 𝑝 0 > 0 such that 𝑝 0 ≤ 𝑝ℎ★. Setting 𝑔(𝑛) = ⌊𝑛𝑝 0 /2⌋ and choosing any 𝑓 , ℎ with 𝑓 (𝑛) ≥ 𝑖 ★, ℎ(𝑛) ≥ 2 𝑖 (C, D), and log(𝑓 (𝑛) ℎ(𝑛)) = 𝑜 (𝑛), the generation error satisfies gen GenErr(A𝜀,𝑓 ,𝑔,ℎ , D, C, 𝑛) ≲ exp − min{1, 𝜀} · 𝑛 . Proof. Since 𝑝 0 ≤ 𝑝ℎ★, we have 𝑔(𝑛) = ⌊𝑛𝑝 0 /2⌋ ≤ 𝑛𝑝ℎ★/2, satisfying condition (ii) of Theorem E.20. For the coverage term: |𝐼ℎ★ | is a constant and 𝑝ℎ★ ≥ 𝑝 0 > 0, so |𝐼ℎ★ | exp(−𝑛𝑝ℎ★/8) ≤ |𝐼ℎ★ | exp(−𝑛𝑝 0 /8) = exp(−Ω(𝑛)). For the privacy term: 𝑔(𝑛) ≥ 𝑛𝑝 0 /4 for large 𝑛, so 𝜀𝑛𝑝 𝜀 𝑔(𝑛) 0 ≤ 𝑓 (𝑛) ℎ(𝑛) exp − . 𝑓 (𝑛) ℎ(𝑛) exp − 8 32 Since log(𝑓 (𝑛) ℎ(𝑛)) = 𝑜 (𝑛), the prefactor is absorbed into the exponential, giving exp(−Ω(𝜀𝑛)). The collision term is exp(−𝑛/2) = exp(−Ω(𝑛)). Taking the maximum, all three terms are exp(−Ω(min{1, 𝜀} · 𝑛)). □ Corollary E.22 (Rate without Known Mass Floor, Restatement of Corollary 4.8). Under the conditions of Theorem E.20, for any 𝑟 (𝑛) with 𝑟 (𝑛) → ∞ and 𝑟 (𝑛) = 𝑜 (𝑛), setting 𝑔(𝑛) = ⌊𝑟 (𝑛)⌋ and choosing 𝑓 , ℎ with log(𝑓 (𝑛) ℎ(𝑛)) = 𝑜 (𝑟 (𝑛)), the generation error satisfies gen GenErr(A𝜀,𝑓 ,𝑔,ℎ , D, C, 𝑛) ≲ exp −𝜀 · 𝑟 (𝑛) . Proof. The coverage term satisfies |𝐼ℎ★ | exp(−𝑛𝑝ℎ★/8) ≤ |𝐼ℎ★ | exp(−𝑟 (𝑛)/4) since 𝑛𝑝ℎ★ ≥ 2𝑟 (𝑛). The privacy term satisfies 𝑓 (𝑛) ℎ(𝑛) exp(−𝜀 𝑟 (𝑛)/8). Since log(𝑓 (𝑛) ℎ(𝑛)) = 𝑜 (𝑟 (𝑛)), the prefactor is absorbed, giving exp(−Ω(𝜀 𝑟 (𝑛))). □

E.3

Proof of Theorem 4.9 (Approximate DP Generation)

E.3.1

Privacy Analysis.

Lemma E.23 (ℓ2 -Sensitivity of 𝑞 pair ). Define 𝑣 : U𝑛 → ℝ 𝑓 (𝑛) ·ℎ (𝑛) by 𝑣 (𝑆) := (𝑞 pair (𝑆, (𝑖, 𝑡))) (𝑖,𝑡 ) ∈ [ 𝑓 (𝑛) ] × [ℎ (𝑛) ] . √︁ (𝑛) Then 𝑣 has ℓ2 -sensitivity ℎ𝑔 (𝑛) 𝑓 (𝑛) · ℎ(𝑛).

gen

Algorithm 7 Approximate DP Generation without a Public Witness Bound A𝜀,𝛿,𝑓 ,𝑔,ℎ Require: Dataset 𝑆 = (𝑥 1, . . . , 𝑥𝑛 ) ∈ U𝑛 , privacy parameters 𝜀 > 0, 𝛿 ∈ (0, 1), functions 𝑓 , 𝑔, ℎ : ℕ → ℕ, language collection C = {𝐿𝑖 }𝑖 ∈ℕ . Ensure: A string 𝑥b ∈ U. 1: for 𝑘 ∈ [ℎ(𝑛)] do Í 2: 𝑁𝑆 (𝑢𝑘 ) ← 𝑛𝑡=1 1{𝑥𝑡 = 𝑢𝑘 } 3: end for 4: for 𝑖 ∈ [𝑓 (𝑛)], 𝑡 ∈ [ℎ(𝑛)] do 5: Compute 𝐼𝑖 (𝑡), 𝑎𝑖,𝑡 (𝑆), 𝑑𝑖,𝑡 (𝑆), 𝑞 pair (𝑆, (𝑖, 𝑡)) via (E.7)–(E.10) 6: end for √ 𝑓 (𝑛) ·ℎ (𝑛) √︁ ℎ (𝑛) 2 log(1.25/𝛿) 7: 𝜎 ← 𝑔 (𝑛) · 𝜀 8: for (𝑖, 𝑡) ∈ [𝑓 (𝑛)] × [ℎ(𝑛)] do 9: Sample 𝑍𝑖,𝑡 ∼ N (0, 𝜎 2 ) 10: 𝑞epair (𝑆, (𝑖, 𝑡)) ← 𝑞 pair (𝑆, (𝑖, 𝑡)) + 𝑍𝑖,𝑡 11: end for 12: (b 𝑖, b 𝑡 ) ← arg max (𝑖,𝑡 ) ∈ [ 𝑓 (𝑛) ] × [ℎ (𝑛) ] 𝑞epair (𝑆, (𝑖, 𝑡)) 13: Sample b 𝑗 ∼ Unif ( [2𝑛 ]) ⊲ Public randomness b 14: return the 𝑗 -th smallest-indexed string in 𝐿b 𝑡 +2, . . .} 𝑡 +1, 𝑢b 𝑖 ∩ {𝑢b Proof. By Lemma E.14, each coordinate satisfies |𝑞 pair (𝑆, (𝑖, 𝑡)) −𝑞 pair (𝑆 ′, (𝑖, 𝑡))| ≤ ℎ(𝑛)/𝑔(𝑛) for neighboring 𝑆, 𝑆 ′ . Therefore ∑︁ ℎ(𝑛) 2 . ∥𝑣 (𝑆) − 𝑣 (𝑆 ′ ) ∥ 22 = |𝑞 pair (𝑆, (𝑖, 𝑡)) − 𝑞 pair (𝑆 ′, (𝑖, 𝑡))| 2 ≤ 𝑓 (𝑛) · ℎ(𝑛) · 𝑔(𝑛) 2 (𝑖,𝑡 )

√︁ (𝑛) Taking the square root gives ∥𝑣 (𝑆) − 𝑣 (𝑆 ′ ) ∥ 2 ≤ ℎ𝑔 (𝑛) 𝑓 (𝑛) · ℎ(𝑛).

□

Lemma E.24 (Privacy). Algorithm 7 is (𝜀, 𝛿)-differentially private. √︁ (𝑛) Proof. By Lemma E.23, the pair score vector has ℓ2 -sensitivity Δ2 = ℎ𝑔 (𝑛) 𝑓 (𝑛) · ℎ(𝑛). The Gaussian √︁ mechanism with 𝜎 = Δ𝜀2 2 log(1.25/𝛿) ensures the noisy score vector is (𝜀, 𝛿)-DP. The subsequent steps are post-processing and therefore (𝜀, 𝛿)-DP by Lemma 2.3. □ E.3.2

Utility Analysis.

The utility analysis proceeds as in the pure DP case: (i) coverage (Lemma E.17, unchanged); (ii) noise concentration (Lemma E.25); (iii) deterministic correctness on the intersection of both events (Lemma E.26). Lemma E.25 (Noise Concentration). Suppose ℎ(𝑛) ≥ 2 𝑖 (C, D). Define the event n o ℎ(𝑛) Gℎ := |𝑍𝑖,𝑡 | ≤ ∀ (𝑖, 𝑡) ∈ [𝑓 (𝑛)] × [ℎ(𝑛)] . 8 Then Pr[Gℎ𝑐 ] ≤ 2𝑓 (𝑛) ℎ(𝑛) exp −

𝜀 2 𝑔(𝑛) 2 . 256 𝑓 (𝑛) ℎ(𝑛) log(1.25/𝛿)

Proof. Each 𝑍𝑖,𝑡 ∼ N (0, 𝜎 2 ) with 𝜎2 =

2ℎ(𝑛) 2 𝑓 (𝑛) ℎ(𝑛) log(1.25/𝛿) 2ℎ(𝑛) 3 𝑓 (𝑛) log(1.25/𝛿) = . 𝜀 2𝑔(𝑛) 2 𝜀 2𝑔(𝑛) 2 37

By the Gaussian tail bound (Lemma B.3), h ℎ(𝑛) 2 /64 𝜀 2𝑔(𝑛) 2 ℎ(𝑛) i Pr |𝑍𝑖,𝑡 | > ≤ 2 exp − = 2 exp − . 8 2𝜎 2 256 𝑓 (𝑛) ℎ(𝑛) log(1.25/𝛿) A union bound over 𝑓 (𝑛) · ℎ(𝑛) pairs gives the result.

□

Lemma E.26 (Deterministic Correctness on Eℎ ∩ Gℎ ). Suppose ℎ(𝑛) ≥ 2 𝑖 (C, D). On the event Eℎ ∩ Gℎ , Algorithm 7 selects a good language, i.e., 𝐿b𝑖 ⊆ supp(D). Proof. Assume Eℎ ∩ Gℎ holds. By Lemma E.18, 𝑞 pair (𝑆, (𝑖 ★, ℎ(𝑛))) = ℎ(𝑛) and every bad pair (𝑖, 𝑡) satisfies 𝑞 pair (𝑆, (𝑖, 𝑡)) ≤ 𝑖 (C, D) − 1 ≤ ℎ(𝑛)/2 − 1. For the good pair (𝑖 ★, ℎ(𝑛)): 𝑞epair (𝑆, (𝑖 ★, ℎ(𝑛))) = ℎ(𝑛) + 𝑍𝑖★,ℎ (𝑛) ≥ ℎ(𝑛) −

ℎ(𝑛) 7ℎ(𝑛) = . 8 8

For any bad pair (𝑖, 𝑡): 𝑞epair (𝑆, (𝑖, 𝑡)) ≤

ℎ(𝑛) 5ℎ(𝑛) ℎ(𝑛) −1+ = − 1. 2 8 8

Since 7ℎ(𝑛)/8 > 5ℎ(𝑛)/8 − 1 for ℎ(𝑛) ≥ 4, the argmax must select a good pair. E.3.3

□

Putting Things Together.

Theorem E.27 (Guarantees of Algorithm 7). Let C = {𝐿𝑖 }𝑖 ∈ℕ be a countable collection of infinite languages and let D be any distribution over U. Suppose Assumptions E.2 and E.3 hold. Let 𝜀 > 0, 𝛿 ∈ (0, 1), and let 𝑓 , 𝑔, ℎ : ℕ → ℕ satisfy: (i) 𝑓 (𝑛) ≥ 𝑖 ★ and ℎ(𝑛) ≥ 2 𝑖 (C, D) for all large enough 𝑛; (ii) 𝑔(𝑛) → ∞ and 𝑔(𝑛) ≤ 𝑛𝑝ℎ★/2 for all large enough 𝑛. Then for all sufficiently large 𝑛, Algorithm 7 has the following guarantees: • Privacy. Algorithm 7 is (𝜀, 𝛿)-differentially private. • Utility. The generation error satisfies 𝑛𝑝 ★ 𝑛 𝜀 2𝑔(𝑛) 2 gen ★ GenErr(A𝜀,𝛿,𝑓 ,𝑔,ℎ , D, C, 𝑛) ≤ |𝐼ℎ | exp − ℎ + 2𝑓 (𝑛)ℎ(𝑛) exp − + exp − . 8 256𝑓 (𝑛)ℎ(𝑛) log(1.25/𝛿) 2 (E.13) Proof. Privacy. This follows from Lemma E.24. Utility. By Lemma E.26, 𝐿b𝑖 ⊆ supp(D) whenever Eℎ ∩ Gℎ holds. By a union bound: GenErr ≤ Pr[Eℎ𝑐 ] + Pr[Gℎ𝑐 ] + Pr[b 𝑥 ∈ 𝑆 | 𝐿b𝑖 ⊆ supp(D)]. Applying Lemma E.17, Lemma E.25, and the collision bound 𝑛/2𝑛 ≤ exp(−𝑛/2): 𝑛𝑝 ★ ℎ

GenErr ≤ |𝐼ℎ★ | exp −

+ 2𝑓 (𝑛) ℎ(𝑛) exp −

𝑛 𝜀 2𝑔(𝑛) 2 + exp − . 256 𝑓 (𝑛) ℎ(𝑛) log(1.25/𝛿) 2 □

Corollary E.28 (Privacy is Essentially Free). Under the conditions of Theorem E.27, suppose the learner is given a constant 𝑝 0 > 0 with 𝑝 0 ≤ 𝑝ℎ★. Setting 𝑔(𝑛) = ⌊𝑛𝑝 0 /2⌋ and choosing any 𝑓 , ℎ with 𝑓 (𝑛) ≥ 𝑖 ★, ℎ(𝑛) ≥ 2 𝑖 (C, D), and log(𝑓 (𝑛) ℎ(𝑛)) = 𝑜 (𝑛), the generation error satisfies gen

GenErr(A𝜀,𝛿,𝑓 ,𝑔,ℎ , D, C, 𝑛) ≲ exp(−Ω(𝑛)) for any constant 𝜀 > 0 and 𝛿 ≥ exp(−poly(𝑛)). Proof. The coverage term is |𝐼ℎ★ | exp(−𝑛𝑝ℎ★/8) = exp(−Ω(𝑛)). For the privacy term, substituting 𝑔(𝑛) ≥ 𝑛𝑝 0 /4 gives 𝜀 2𝑝 02𝑛 2 𝜀 2𝑔(𝑛) 2 ≥ . 256 𝑓 (𝑛) ℎ(𝑛) log(1.25/𝛿) 4096 𝑓 (𝑛) ℎ(𝑛) log(1.25/𝛿) Since 𝑓 (𝑛) ℎ(𝑛) = 𝑜 (𝑛/log 𝑛) (ensured by log(𝑓 (𝑛) ℎ(𝑛)) = 𝑜 (𝑛)) and log(1.25/𝛿) = poly(log 𝑛) for 𝛿 ≥ exp(−poly(𝑛)), the exponent is 𝜔 (𝑛) for constant 𝜀, 𝑝 0 . The prefactor 2𝑓 (𝑛) ℎ(𝑛) is absorbed. The collision term is exp(−𝑛/2). All three terms are exp(−Ω(𝑛)). □ Remark E.29 (Summary: Approximate DP Generation). Approximate DP generation achieves the nonprivate rate exp(−Ω(𝑛)) for any constant 𝜀 > 0 and 𝛿 ≥ exp(−poly(𝑛)), in both the public-bound and no-public-bound settings. The privacy cost only appears when 𝜀 = 𝑂 (𝑛 −3/4 log1/4 𝑛) (with typical parameter choices), which is qualitatively different from pure DP where it appears at 𝜀 = 𝑂 (1). This contrasts with pure DP generation (exp(−𝜀𝑛) for 𝜀 < 1), approximate DP identification (exp(−𝑜 (𝑛)) only), and pure DP identification (exp(− min{1, 𝜀} · 𝑜√︁ (𝑛))). The fundamental reason is that generation scores have constant sensitivity, so Gaussian noise 𝜎 ∝ 𝑓 (𝑛)/𝜀 is negligible relative to the score gap 𝑔(𝑛) ∝ 𝑛.

Proofs for Section 5 (Lower Bounds)

F.1

Proof of Theorem 5.4 (Lower Bound for DP Identification)

We establish a lower bound showing that the exponential dependence on min{1, 𝜀} ·𝑛 in our upper bounds is information-theoretically necessary. The proof proceeds in four steps: (i) we introduce a structural condition on the language collection (the IPP condition) and construct a hard instance from it (Definitions F.1–F.3); (ii) we establish properties of the hard instance and relate identification error to misidentification probability (Lemmas F.4 and F.5); (iii) we use a coupling argument together with group privacy to show that any 𝜀-DP algorithm must misidentify with probability at least exp(−𝑂 (𝜀𝑛)) (Lemma F.6); (iv) we combine this DP-specific lower bound with the non-private lower bound of Høgsgaard and Pabbaraju [2026] to obtain the final exp(− min{1, 𝜀} · 𝑛) result (Theorem F.9). F.1.1

Hard Instance Construction

Definition F.1 (Private Element). Let C be a collection of languages over U. For a language 𝐿 ∈ C, an element 𝑥 ∈ U is private to 𝐿 with respect to C if Ø e 𝑥 ∈𝐿\ 𝐿 . e C\{𝐿} 𝐿∈

Definition F.2 (Intersecting Private-Pair (IPP) Condition). A collection C of languages satisfies the Intersecting Private-Pair (IPP) Condition if there exist two languages 𝐿, 𝐿 ′ ∈ C such that both have at least one private element with respect to C and 𝐿 ∩ 𝐿 ′ ≠ ∅.

Definition F.3 (Hard Instance). Assume C satisfies IPP. Let 𝐿, 𝐿 ′ ∈ C be two languages witnessing IPP. Fix elements Ø Ø ′ ′ e e 𝑠0 ∈ 𝐿 ∩ 𝐿 , 𝑠1 ∈ 𝐿 \ 𝐿 , 𝑠2 ∈ 𝐿 \ 𝐿 . e C\{𝐿 ′ } 𝐿∈

e C\{𝐿} 𝐿∈

Note that 𝑠 0, 𝑠 1, 𝑠 2 are necessarily distinct (e.g., if 𝑠 1 = 𝑠 0 then 𝑠 1 ∈ 𝐿 ∩ 𝐿 ′ ⊆ 𝐿 ′ , contradicting that 𝑠 1 is private to 𝐿; similarly 𝑠 2 ≠ 𝑠 0 , and 𝑠 1 ≠ 𝑠 2 since 𝑠 1 ∉ 𝐿 ′ while 𝑠 2 ∈ 𝐿 ′ ). Define two distributions D, D ′ over U: 𝑥∼D

𝑥∼D

Pr [𝑥 = 𝑠 1 ] = 14 ,

𝑥∼D

Pr [𝑥 = 𝑠 0 ] = 43 ,

𝑥∼D ′

Pr [𝑥 = 𝑠 2 ] = 41 ,

𝑥∼D ′

D : Pr [𝑥 = 𝑠 0 ] = 43 , D′ : F.1.2

𝑥∼D ′

Pr [𝑥 = 𝑠] = 0 ∀ 𝑠 ∉ {𝑠 0, 𝑠 1 }, Pr [𝑥 = 𝑠] = 0 ∀ 𝑠 ∉ {𝑠 0, 𝑠 2 }.

Properties of the Hard Instance

Lemma F.4 (Optimality and Gap). Consider the hard instance in Definition F.3. Then: e e (a) err D (𝐿) = inf 𝐿∈ e C err D ( 𝐿) = 0 and inf 𝐿∈ e C\{𝐿} err D ( 𝐿) ≥ 1/4. e e (b) err D ′ (𝐿 ′ ) = inf 𝐿∈ e C err D ′ ( 𝐿) = 0 and inf 𝐿∈ e C\{𝐿 ′ } err D ′ ( 𝐿) ≥ 1/4. Proof. We prove part (a), and part (b) follows by the symmetric argument, swapping (𝐿, 𝑠 1, D) with (𝐿 ′, 𝑠 2, D ′ ). Since 𝑠 0 ∈ 𝐿 and 𝑠 1 ∈ 𝐿 by construction, the support of D satisfies supp(D) = {𝑠 0, 𝑠 1 } ⊆ 𝐿. It follows that every draw from D lands in 𝐿, so err D (𝐿) = Pr [𝑥 ∉ 𝐿] = 0. 𝑥∼D

e Since err D (e 𝐿) ≥ 0 for every e 𝐿 ∈ C and the value 0 is achieved by 𝐿, we conclude inf 𝐿∈ e C err D ( 𝐿) = 0. e Now fix any 𝐿 ∈ C \ {𝐿}. By Definition F.1, 𝑠 1 is private to 𝐿 with respect to C, which means 𝑠 1 ∉ e 𝐿 for any e 𝐿 ≠ 𝐿. Since 𝑠 1 ∉ e 𝐿, any draw from D that equals 𝑠 1 is not covered by e 𝐿: 1 err D (e 𝐿) = Pr [𝑥 ∉ e 𝐿] ≥ Pr [𝑥 = 𝑠 1 ] = . 𝑥∼D 𝑥∼D 4 Since this holds for every e 𝐿 ∈ C \ {𝐿}, the infimum over this set is at least 1/4.

□

Lemma F.5 (From Misidentification to Identification error). Consider the hard instance in Definition F.3. For any identification algorithm A (using randomness 𝑟 ), IdErr(A, D, C, 𝑛) ≥

1 · Pr [A (𝑆) ≠ 𝐿], 4 𝑆∼D𝑛 ,𝑟

IdErr(A, D ′, C, 𝑛) ≥

1 · Pr [A (𝑆) ≠ 𝐿 ′ ]. 4 𝑆∼( D ′ ) 𝑛 ,𝑟

Proof. We prove the first inequality; the second follows by the symmetric argument. By Lemma F.4(a), the agnostic optimum under D equals 0 and is uniquely attained by 𝐿 (in the sense that every other language incurs error at least 1/4). Therefore the identification error simplifies to IdErr(A, D, C, 𝑛) = 𝔼𝑛 err D (A (𝑆)) − 0 = 𝔼𝑛 err D (A (𝑆)) . 𝑆∼D ,𝑟

𝑆∼D ,𝑟

We now bound the integrand pointwise by case analysis on the output of A. If A (𝑆) = 𝐿, then supp(D) ⊆ 𝐿 implies err D (A (𝑆)) = err D (𝐿) = 0. If A (𝑆) = e 𝐿 ≠ 𝐿, then e 𝐿 ∈ C \ {𝐿}, so 𝑠 1 ∉ e 𝐿 by privacy of 𝑠 1 . Consequently, 1 err D (e 𝐿) = Pr [𝑥 ∉ e 𝐿] ≥ Pr [𝑥 = 𝑠 1 ] = . 𝑥∼D 𝑥∼D 4 40

Combining both cases, we obtain the pointwise bound err D (A (𝑆)) ≥

1 · 1{A (𝑆) ≠ 𝐿} 4

for every realization of 𝑆 and 𝑟 . Taking expectations over (𝑆, 𝑟 ) on both sides yields 1 1 IdErr(A, D, C, 𝑛) = 𝔼 err D (A (𝑆)) ≥ · 𝔼 1{A (𝑆) ≠ 𝐿} = · Pr𝑛 [A (𝑆) ≠ 𝐿]. 𝑆,𝑟 4 𝑆,𝑟 4 𝑆∼D ,𝑟 □ F.1.3

The DP-Specific Coupling Argument

The next lemma is the technical core of the lower bound. The key idea is to construct a coupling under which the two input distributions D 𝑛 and (D ′ )𝑛 have small Hamming distance with high probability, and then apply group privacy (via Lemma B.5) to constrain how differently any 𝜀-DP algorithm can behave on them. Intuitively, both distributions produce the shared element 𝑠 0 with probability 3/4 at each coordinate, so the expected Hamming distance between coupled samples is only 𝑛/4; yet the algorithm must distinguish 𝐿 from 𝐿 ′ , and differential privacy limits its ability to do so. Lemma F.6 (DP Forces Misidentification). Consider the hard instance in Definition F.3. Let A be an 𝜀differentially private identification algorithm. Define 𝑝 :=

Pr [A (𝑆) = 𝐿],

𝑆∼D𝑛 ,𝑟

𝑞 := ′ Pr′ 𝑛 [A (𝑆 ′ ) = 𝐿 ′ ]. 𝑆 ∼( D ) ,𝑟

Then max{1 − 𝑝, 1 − 𝑞} ≥

𝜀𝑛 1 − exp(−𝑛/12) 1 ≥ exp − . 1 + exp(𝜀𝑛/2) 30 2

Proof. Step 1: Coupling construction. We define a coupling (𝑆 1, 𝑆 2 ) of D 𝑛 and (D ′ )𝑛 that maximizes the overlap between the two samples. For each coordinate 𝑡 ∈ [𝑛], sample (𝑋𝑡 , 𝑌𝑡 ) independently with 1 Pr[(𝑋𝑡 , 𝑌𝑡 ) = (𝑠 1, 𝑠 2 )] = . 4

3 Pr[(𝑋𝑡 , 𝑌𝑡 ) = (𝑠 0, 𝑠 0 )] = , 4

Let 𝑆 1 = (𝑋 1, . . . , 𝑋𝑛 ) and 𝑆 2 = (𝑌1, . . . , 𝑌𝑛 ). To verify that this is a valid coupling, observe that the marginal of 𝑋𝑡 satisfies Pr[𝑋𝑡 = 𝑠 0 ] = 3/4 and Pr[𝑋𝑡 = 𝑠 1 ] = 1/4, which matches D; similarly, the marginal of 𝑌𝑡 satisfies Pr[𝑌𝑡 = 𝑠 0 ] = 3/4 and Pr[𝑌𝑡 = 𝑠 2 ] = 1/4, matching D ′ . Hence 𝑆 1 ∼ D 𝑛 and 𝑆 2 ∼ (D ′ )𝑛 . Step 2: Hamming distance concentration. The Hamming distance between the coupled samples is 𝐻 := 𝑑 Ham (𝑆 1, 𝑆 2 ) =

𝑛 ∑︁

1{𝑋𝑡 ≠ 𝑌𝑡 }.

𝑡 =1

Since 𝑋𝑡 = 𝑌𝑡 if and only if (𝑋𝑡 , 𝑌𝑡 ) = (𝑠 0, 𝑠 0 ) (which occurs with probability 3/4), and 𝑋𝑡 ≠ 𝑌𝑡 otherwise (with probability 1/4), each indicator 1{𝑋𝑡 ≠ 𝑌𝑡 } is an independent Bernoulli(1/4) random variable. Therefore 𝔼[𝐻 ] = 𝑛/4. By the Chernoff bound (Lemma B.2) with 𝑡 = 1, 𝔼[𝐻 ] 𝑛 Pr[𝐻 > 2 𝔼[𝐻 ]] = Pr[𝐻 > 𝑛/2] ≤ exp − = exp − . 3 12 We set 𝐾 = 𝑛/2 and 𝜂 = exp(−𝑛/12), so that Pr[𝐻 > 𝐾] ≤ 𝜂. 41

Step 3: Applying the coupling lemma. We now apply Lemma B.5 to relate the behavior of A under D 𝑛 and (D ′ )𝑛 . Taking F = {𝐿} (the event that the algorithm outputs 𝐿), Lemma B.5 gives 𝑝 = Pr[A (𝑆 1 ) = 𝐿] ≤ 𝑒 𝜀𝐾 Pr[A (𝑆 2 ) = 𝐿] + 𝜂 = 𝑒 𝜀𝑛/2 Pr[A (𝑆 2 ) = 𝐿] + exp(−𝑛/12). Now, since A (𝑆 2 ) outputs some language in C, we have Pr[A (𝑆 2 ) = 𝐿] ≤ 1 − Pr[A (𝑆 2 ) = 𝐿 ′ ] = 1 − 𝑞. Substituting: 𝑝 ≤ 𝑒 𝜀𝑛/2 (1 − 𝑞) + exp(−𝑛/12).

(F.1)

By the symmetric argument with F = {𝐿 ′ }, we obtain 𝑞 ≤ 𝑒 𝜀𝑛/2 (1 − 𝑝) + exp(−𝑛/12).

(F.2)

Step 4: Extracting the bound. Let 𝑠 = min{𝑝, 𝑞}; we aim to upper bound 𝑠. If 𝑠 = 𝑝, then 𝑞 ≥ 𝑠, so 1 − 𝑞 ≤ 1 − 𝑠; substituting into (F.1) gives 𝑠 ≤ 𝑒 𝜀𝑛/2 (1 − 𝑠) + exp(−𝑛/12). If 𝑠 = 𝑞, then 𝑝 ≥ 𝑠, so 1 − 𝑝 ≤ 1 − 𝑠; substituting into (F.2) gives the same inequality. In either case, 𝑠 + 𝑠 · 𝑒 𝜀𝑛/2 ≤ 𝑒 𝜀𝑛/2 + exp(−𝑛/12), which rearranges to 𝑠≤

exp(𝜀𝑛/2) + exp(−𝑛/12) . 1 + exp(𝜀𝑛/2)

Therefore, max{1 − 𝑝, 1 − 𝑞} = 1 − 𝑠 ≥ 1 −

exp(𝜀𝑛/2) + exp(−𝑛/12) 1 − exp(−𝑛/12) = . 1 + exp(𝜀𝑛/2) 1 + exp(𝜀𝑛/2)

(F.3)

It remains to simplify (F.3). For the numerator: since 𝑛 ≥ 1, we have exp(−𝑛/12) ≤ exp(−1/12), and so 1 − exp(−𝑛/12) ≥ 1 − exp(−1/12) >

1 , 15

where the last inequality follows from the numerical bound exp(−1/12) < 1 − 1/15 = 14/15. For the denominator: 1 + exp(𝜀𝑛/2) ≤ 2 exp(𝜀𝑛/2). Combining these two estimates: 𝜀𝑛 1/15 1 . max{1 − 𝑝, 1 − 𝑞} ≥ = exp − 2 exp(𝜀𝑛/2) 30 2 □ F.1.4

Putting Things Together

We first state the DP-specific lower bound, then combine it with the non-private lower bound of Høgsgaard and Pabbaraju [2026]. Theorem F.7 (Lower Bound for DP Identification). Let C be a collection of languages over U satisfying the IPP condition. For any 𝜀-differentially private identification algorithm A, there exists a distribution D★ over U such that 𝜀𝑛 1 IdErr(A, D★, C, 𝑛) ≥ exp − 120 2 for infinitely many 𝑛. 42

Proof. Fix an even integer 𝑛 ≥ 2. Lemma F.6 applied to the hard instance from Definition F.3 gives n o 𝜀𝑛 1 max Pr𝑛 [A (𝑆) ≠ 𝐿], Pr′ 𝑛 [A (𝑆) ≠ 𝐿 ′ ] ≥ exp − . 𝑆∼D ,𝑟 30 2 𝑆∼( D ) ,𝑟 Applying Lemma F.5 to both distributions, each identification error is at least 1/4 times the corresponding misidentification probability: 𝜀𝑛 𝜀𝑛 1 1 1 = . max IdErr(A, D, C, 𝑛), IdErr(A, D ′, C, 𝑛) ≥ · exp − exp − 4 30 2 120 2 This holds for every even 𝑛 ≥ 2. Since there are infinitely many even integers but only two candidate distributions D and D ′ , the pigeonhole principle guarantees the existence of a fixed distribution D★ ∈ {D, D ′ } for which the bound holds along an infinite subsequence of even integers. □ Theorem F.7 captures the cost of privacy: the exp(−𝜀𝑛/2) barrier is specific to 𝜀-DP algorithms. However, when 𝜀 is large (e.g., 𝜀 ≥ 1), this bound decays faster than exp(−𝑛/2) and becomes weaker than what is possible even without any privacy constraint. To obtain a lower bound that is meaningful across all privacy regimes, we combine Theorem F.7 with the information-theoretic lower bound in Høgsgaard and Pabbaraju [2026], which applies to all algorithms regardless of whether they satisfy differential privacy. Theorem F.8 (Lower Bound for Agnostic Language Identification, Theorem 2.2 in Høgsgaard and Pabbaraju [2026]). Let C be any collection of languages over a universe U satisfying that there exist 𝐿, 𝐿 ′ ∈ C with both Ð Ð ′ e e 𝐿 \ ( 𝐿∈ e C\{𝐿} 𝐿) ≠ ∅ and 𝐿 \ ( 𝐿∈ e C\{𝐿 ′ } 𝐿) ≠ ∅. Then, for any identification algorithm A using randomness e 𝑟 , there exists a distribution D over U such that there exists 𝐿★ ∈ C with err D (𝐿★) = inf 𝐿∈ e C err D ( 𝐿), and furthermore IdErr(A, D, C, 𝑛) ≥ exp(−5𝑛) for infinitely many 𝑛. Theorem F.9 (Lower Bound for DP Identification, all Regimes). Let C be a collection of languages over U satisfying the IPP condition. For any 𝜀-differentially private identification algorithm A, there exists a distribution D★ over U such that IdErr(A, D★, C, 𝑛) ≥ exp −5 min{1, 𝜀} · 𝑛) for infinitely many 𝑛. Proof. We consider two regimes depending on the privacy parameter 𝜀. Case 1: 𝜀 < 1. By Theorem F.7, there exists a distribution D★ over U such that 𝜀𝑛 1 IdErr(A, D★, C, 𝑛) ≥ exp − 120 2 for infinitely many 𝑛. Since 𝜀 < 1, we have min{1, 𝜀} = 𝜀. Note that 𝜀𝑛 𝜀𝑛 𝜀𝑛 19𝜀𝑛 1 exp − = exp − − log 120 ≥ exp − − = exp(−5𝜀𝑛), 120 2 2 2 4 where the inequality is due to log 120 ≤ 19𝜀𝑛/4 for sufficiently large 𝑛. Case 2: 𝜀 ≥ 1. Every 𝜀-DP algorithm is in particular a (possibly randomized) identification algorithm, so information-theoretic lower bounds apply without modification. Note that the IPP condition (Definition F.2) implies the assumptions of Theorem F.8. Hence there exists a distribution D★ over U such that IdErr(A, D★, C, 𝑛) ≥ exp(−5𝑛) for infinitely many 𝑛.

□ 43

Remark F.10 (Tightness). Comparing Theorem F.9 with the upper bound in Corollary D.9: the upper bound achieves exp(− min{1, 𝜀} · 𝑟 (𝑛)) for any 𝑟 (𝑛) = 𝑜 (𝑛) with 𝑟 (𝑛) → ∞, while the lower bound requires exp(− min{1, 𝜀} · 𝑛). The dependence on min{1, 𝜀} is therefore tight since privacy costs exactly a multiplicative factor of 𝜀 in the exponent when 𝜀 < 1, and is free when 𝜀 ≥ 1. The remaining gap between 𝑜 (𝑛) and 𝑂 (𝑛) in the exponent is inherited from the non-private setting [Høgsgaard and Pabbaraju, 2026], where closing it remains an open problem.

F.2

Proof of Theorem 5.6 (Lower Bound for DP Generation)

We establish a lower bound showing that the exponential dependence on min{1, 𝜀} · 𝑛 in our generation upper bounds is information-theoretically necessary. The proof structure parallels the identification lower bound (Section D.1), but with two key differences: (i) the hard distributions must have infinite supports (since generation requires producing novel strings from an infinite support), necessitating a stronger structural condition on the collection; (ii) the argument is inherently asymmetric—under D, the algorithm should output strings from 𝐿 \ 𝐿 ′ , while under D ′ , such outputs constitute failures—and we exploit this asymmetry through a one-sided application of the coupling lemma. F.2.1

Hard Instance Construction

Definition F.11 (Intersecting Infinite-Difference Pair (IIDP)). A collection C of languages over a countable universe U satisfies the Intersecting Infinite-Difference Pair (IIDP) condition if there exist two distinct languages 𝐿, 𝐿 ′ ∈ C, an element 𝑠 0 ∈ 𝐿 ∩ 𝐿 ′ , and two infinite sequences of distinct elements (𝑎𝑘 )𝑘 ≥1 ⊆ 𝐿 \ 𝐿 ′ and (𝑏𝑘 )𝑘 ≥1 ⊆ 𝐿 ′ \ 𝐿. Remark F.12 (On the Structural Conditions). The IIDP condition (Definition F.11) strengthens the IPP condition used for identification (Definition F.2) by requiring infinitely many private elements on each side, which is necessary because the generation lower bound needs hard distributions with infinite supports. The combined lower bound also requires the condition of Theorem F.20 (Theorem 3.4 in Høgsgaard and Pabbaraju [2026]); this is logically independent of IIDP, but both can be satisfied simultaneously, either by different pairs within C, or by a single pair (𝐿, 𝐿 ′ ) when 𝐿 ∩ 𝐿 ′ is finite (e.g., in regular or context-free languages). Definition F.13 (Hard Instance for Generation). Assume C satisfies IIDP and witnessed by (𝐿, 𝐿 ′, 𝑠 0, (𝑎𝑘 )𝑘 ≥1, (𝑏𝑘 )𝑘 ≥1 ). Define distributions D and D ′ over U by D : Pr [𝑥 = 𝑠 0 ] = 34 , D′ :

Pr [𝑥 = 𝑎𝑘 ] = 41 · 2−𝑘

(𝑘 ≥ 1),

Pr [𝑥 = 𝑏𝑘 ] = 14 · 2−𝑘

(𝑘 ≥ 1).

𝑥∼D

Pr [𝑥 = 𝑠 0 ] = 34 ,

𝑥∼D ′

All other strings have zero probability under both distributions. F.2.2

Properties of the Hard Instance

Lemma F.14 (Support structure). Consider the hard instance in Definition F.13. Then: (a) supp(D) = {𝑠 0 } ∪ {𝑎𝑘 : 𝑘 ≥ 1} ⊆ 𝐿 and supp(D ′ ) = {𝑠 0 } ∪ {𝑏𝑘 : 𝑘 ≥ 1} ⊆ 𝐿 ′ . (b) Both supports are infinite. (c) The sets F := {𝑎𝑘 : 𝑘 ≥ 1} and F ′ := {𝑏𝑘 : 𝑘 ≥ 1} satisfy F ∩ supp(D ′ ) = ∅ and F ′ ∩ supp(D) = ∅.

Proof. Part (a): By construction, 𝑠 0 ∈ 𝐿∩𝐿 ′ and 𝑎𝑘 ∈ 𝐿\𝐿 ′ for all 𝑘 ≥ 1, so supp(D) = {𝑠 0 }∪{𝑎𝑘 : 𝑘 ≥ 1} ⊆ 𝐿. The argument for D ′ is symmetric. Part (b): The sequences (𝑎𝑘 )𝑘 ≥1 and (𝑏𝑘 )𝑘 ≥1 are infinite by the IIDP condition, and each element receives positive probability. Part (c): Since 𝑎𝑘 ∈ 𝐿 \ 𝐿 ′ for all 𝑘, we have 𝑎𝑘 ∉ 𝐿 ′ , hence 𝑎𝑘 ∉ {𝑠 0 } ∪ {𝑏 𝑗 : 𝑗 ≥ 1} = supp(D ′ ). Thus F ∩ supp(D ′ ) = ∅. The argument for F ′ is symmetric. □ Lemma F.15 (Disjointness of private elements and opposing support). Consider the hard instance in Definition F.13. Let F = {𝑎𝑘 : 𝑘 ≥ 1}. For any generation algorithm A, {A (𝑆 ′ ) ∈ F } ⊆ {A (𝑆 ′ ) ∉ supp(D ′ ) \ 𝑆 ′ }, where 𝑆 ′ ∼ (D ′ )𝑛 . In other words, if A (𝑆 ′ ) outputs an element of F , it necessarily fails under D ′ . Consequently, Pr[A (𝑆 ′ ) ∈ F ] ≤ GenErr(A, D ′, C, 𝑛). Proof. By Lemma F.14(c), F ∩ supp(D ′ ) = ∅. If A (𝑆 ′ ) ∈ F , then A (𝑆 ′ ) ∉ supp(D ′ ), which immediately implies A (𝑆 ′ ) ∉ supp(D ′ ) \ 𝑆 ′ . Taking probabilities gives the claimed inequality. □ Lemma F.16 (Success under D requires outputting from F ). Consider the hard instance in Definition F.13. Let F = {𝑎𝑘 : 𝑘 ≥ 1}. For any generation algorithm A and 𝑆 ∼ D 𝑛 , Pr[A (𝑆) ∈ F ] ≥ 1 − GenErr(A, D, C, 𝑛) − 4−𝑛 . Proof. By Lemma F.14(a), supp(D) = {𝑠 0 } ∪ F . Hence the success event decomposes as {A (𝑆) ∈ supp(D) \ 𝑆 } ⊆ {A (𝑆) ∈ F } ∪ {A (𝑆) = 𝑠 0, 𝑠 0 ∉ 𝑆 } ⊆ {A (𝑆) ∈ F } ∪ {𝑠 0 ∉ 𝑆 }. Indeed, if A (𝑆) = 𝑠 0 , this output is successful only if 𝑠 0 ∉ 𝑆. Taking probabilities and rearranging: 1 − GenErr(A, D, C, 𝑛) = Pr[A (𝑆) ∈ supp(D) \ 𝑆] ≤ Pr[A (𝑆) ∈ F ] + Pr[𝑠 0 ∉ 𝑆]. Since Pr𝑥∼D [𝑥 = 𝑠 0 ] = 3/4, the probability that 𝑠 0 never appears in 𝑛 i.i.d. draws is Pr[𝑠 0 ∉ 𝑆] = (1 − 3/4)𝑛 = 4−𝑛 . Rearranging gives the claim. □ F.2.3

The DP-Specific Coupling Argument

The next lemma is the technical core of the generation lower bound. As in the identification case, we construct a coupling under which D 𝑛 and (D ′ )𝑛 have small Hamming distance with high probability, and apply the coupling lemma (Lemma B.5). However, the argument is asymmetric: rather than bounding misidentification probabilities in both directions, we combine a lower bound on Pr[A (𝑆) ∈ F ] (from the success requirement under D, Lemma F.16) with an upper bound on Pr[A (𝑆) ∈ F ] (from DP and the failure implication under D ′ , Lemma F.15). Lemma F.17 (DP forces generation error). Consider the hard instance in Definition F.13. Let A be an 𝜀-differentially private generation algorithm. Define 𝛼 := max GenErr(A, D, C, 𝑛), GenErr(A, D ′, C, 𝑛) . Then for every even 𝑛 ≥ 2, 𝛼≥

1 − 4−𝑛 − 𝑒 −𝑛/12 . 1 + 𝑒 𝜀𝑛/2 45

Proof. Let 𝑆 = (𝑋 1, . . . , 𝑋𝑛 ) ∼ D 𝑛 and 𝑆 ′ = (𝑌1, . . . , 𝑌𝑛 ) ∼ (D ′ )𝑛 , and let F = {𝑎𝑘 : 𝑘 ≥ 1}. We derive an upper bound and a lower bound on Pr[A (𝑆) ∈ F ] and combine them. Step 1: Coupling construction. Define a coupling (𝑆 1, 𝑆 2 ) of D 𝑛 and (D ′ )𝑛 coordinate-wise: for each 𝑡 ∈ [𝑛], independently sample (𝑋𝑡 , 𝑌𝑡 ) as follows. With probability 3/4, set (𝑋𝑡 , 𝑌𝑡 ) = (𝑠 0, 𝑠 0 ). With probability 1/4, draw 𝐾𝑡 ∈ ℕ with Pr[𝐾𝑡 = 𝑘] = 2−𝑘 and set (𝑋𝑡 , 𝑌𝑡 ) = (𝑎𝐾𝑡 , 𝑏 𝐾𝑡 ). To verify this is a valid coupling: the marginal of 𝑋𝑡 satisfies Pr[𝑋𝑡 = 𝑠 0 ] = 3/4 and Pr[𝑋𝑡 = 𝑎𝑘 ] = (1/4) · 2−𝑘 for each 𝑘 ≥ 1, matching D. Similarly, the marginal of 𝑌𝑡 satisfies Pr[𝑌𝑡 = 𝑠 0 ] = 3/4 and Pr[𝑌𝑡 = 𝑏𝑘 ] = (1/4) · 2−𝑘 , matching D ′ . Í Step 2: Hamming distance concentration. The Hamming distance 𝐻 := 𝑑 Ham (𝑆 1, 𝑆 2 ) = 𝑛𝑡=1 1{𝑋𝑡 ≠ 𝑌𝑡 } is a sum of 𝑛 independent Bernoulli(1/4) random variables (since 𝑋𝑡 ≠ 𝑌𝑡 if and only if the second branch occurs), so 𝔼[𝐻 ] = 𝑛/4. By the Chernoff bound (Lemma B.2) with 𝑡 = 1, 𝑛 𝔼[𝐻 ] = exp − . Pr[𝐻 > 𝑛/2] = Pr[𝐻 > 2 𝔼[𝐻 ]] ≤ exp − 3 12 Set 𝐾 = 𝑛/2 and 𝜂 = exp(−𝑛/12). Step 3: Upper bound on Pr[A (𝑆) ∈ F ] via DP. By the coupling lemma (Lemma B.5) applied with the measurable set F , Pr[A (𝑆 1 ) ∈ F ] ≤ 𝑒 𝜀𝐾 Pr[A (𝑆 2 ) ∈ F ] + 𝜂 = 𝑒 𝜀𝑛/2 Pr[A (𝑆 2 ) ∈ F ] + 𝑒 −𝑛/12 . By Lemma F.15, Pr[A (𝑆 2 ) ∈ F ] ≤ GenErr(A, D ′, C, 𝑛) ≤ 𝛼. Substituting: Pr[A (𝑆) ∈ F ] ≤ 𝑒 𝜀𝑛/2𝛼 + 𝑒 −𝑛/12 .

(F.4)

Step 4: Lower bound on Pr[A (𝑆) ∈ F ] via success. By Lemma F.16 and the definition of 𝛼, Pr[A (𝑆) ∈ F ] ≥ 1 − GenErr(A, D, C, 𝑛) − 4−𝑛 ≥ 1 − 𝛼 − 4−𝑛 .

(F.5)

Step 5: Combining the bounds. Chaining (F.5) and (F.4): 1 − 𝛼 − 4−𝑛 ≤ Pr[A (𝑆) ∈ F ] ≤ 𝑒 𝜀𝑛/2𝛼 + 𝑒 −𝑛/12 . Rearranging: 1 − 4−𝑛 − 𝑒 −𝑛/12 ≤ (1 + 𝑒 𝜀𝑛/2 ) 𝛼, which gives 𝛼≥

1 − 4−𝑛 − 𝑒 −𝑛/12 . 1 + 𝑒 𝜀𝑛/2 □

Remark F.18 (Asymmetry with the Identification Lower Bound). In the identification lower bound (Lemma F.6), the argument is symmetric: both 𝑝 and 𝑞 are bounded via the coupling lemma, yielding two inequalities that constrain min{𝑝, 𝑞}. In the generation lower bound, the argument is inherently one-sided: the lower bound on Pr[A (𝑆) ∈ F ] comes from the success requirement under D (not from DP), while the upper bound comes from DP applied to the event F combined with the failure implication under D ′ . This asymmetry reflects the fact that the generation objective depends on supp(D), creating a natural directionality between the two distributions. 46

F.2.4

Putting Things Together

Theorem F.19 (Lower Bound for DP Generation). Let C satisfy the IIDP condition (Definition F.11). For any 𝜀-differentially private generation algorithm A, there exists a distribution D★ ∈ {D, D ′ } (from Definition F.13) such that 𝜀𝑛 1 GenErr(A, D★, C, 𝑛) ≥ exp − 4 2 for infinitely many 𝑛. Proof. By Lemma F.17, for every even 𝑛 ≥ 2, 1 − 4−𝑛 − 𝑒 −𝑛/12 max GenErr(A, D, C, 𝑛), GenErr(A, D ′, C, 𝑛) ≥ . 1 + 𝑒 𝜀𝑛/2 We simplify the right-hand side for large 𝑛. For the numerator: 4−𝑛 ≤ 1/16 and 𝑒 −𝑛/12 ≤ 𝑒 −1/6 < 1/6 for all 𝑛 ≥ 2, so 1 − 4−𝑛 − 𝑒 −𝑛/12 ≥ 1 − 1/16 − 1/6 > 1/2. More precisely, as 𝑛 → ∞, 1 − 4−𝑛 − 𝑒 −𝑛/12 → 1. For the denominator: 1 + 𝑒 𝜀𝑛/2 ≤ 2𝑒 𝜀𝑛/2 . Combining, for all sufficiently large even 𝑛: 𝜀𝑛 1 − 4−𝑛 − 𝑒 −𝑛/12 1/2 1 ≥ = exp − . 2 1 + 𝑒 𝜀𝑛/2 2𝑒 𝜀𝑛/2 4 Since this holds for all sufficiently large even 𝑛, and there are only two candidate distributions D and D ′ , the pigeonhole principle guarantees the existence of a fixed D★ ∈ {D, D ′ } for which the bound holds along an infinite subsequence of even 𝑛. □ As in the identification case, Theorem F.19 captures the privacy-specific barrier exp(−𝜀𝑛/2), which becomes vacuously weak when 𝜀 is large. We now combine it with the non-private generation lower bound from Høgsgaard and Pabbaraju [2026] to obtain a bound that is meaningful across all privacy regimes. Theorem F.20 (Lower Bound for Agnostic Language Generation, Theorem 3.4 in Høgsgaard and Pabbaraju [2026]). Let C be any collection over a universe U such that there exist languages 𝐿, 𝐿 ′ ∈ C with |𝐿 ∩ 𝐿 ′ | < ∞ and U \ (𝐿 ∪ 𝐿 ′ ) ≠ ∅. For any generation algorithm A using randomness 𝑟 , there exists a distribution D over U such that ∃ 𝐿 ∈ C with 𝐿 ⊆ supp(D), and furthermore GenErr(A, D, C, 𝑛) ≥

1 exp(−2𝑛) 4

for infinitely many 𝑛. Theorem F.21 (Combined Lower Bound for DP Generation). Let C be a collection of languages over U that satisfies both the IIDP condition (Definition F.11) and the condition of Theorem F.20 (i.e., there exist 𝐿, 𝐿 ′ ∈ C with |𝐿 ∩ 𝐿 ′ | < ∞ and U \ (𝐿 ∪ 𝐿 ′ ) ≠ ∅). For any 𝜀-differentially private generation algorithm A, there exists a distribution D★ over U such that GenErr(A, D★, C, 𝑛) ≥

1 exp(−2 min{1, 𝜀} · 𝑛) 4

for infinitely many 𝑛. Proof. We consider two regimes depending on the privacy parameter 𝜀. Case 1: 𝜀 < 1. By Theorem F.19, there exists D★ such that GenErr(A, D★, C, 𝑛) ≥ 14 exp(−𝜀𝑛/2) for infinitely many 𝑛. Since min{1, 𝜀} = 𝜀, we have 𝜀𝑛 𝜀𝑛 1 exp − = exp − − log 4 ≥ exp(−2𝜀𝑛) 4 2 2 47

where the last inequality is due to that log 4 ≤ 3𝜀𝑛/2 holds for sufficiently large 𝑛. Case 2: 𝜀 ≥ 1. Every 𝜀-DP algorithm is in particular a randomized algorithm. By Theorem F.20, there exists D★ such that GenErr(A, D★, C, 𝑛) ≥ 14 exp(−2𝑛) for infinitely many 𝑛. Since min{1, 𝜀} = 1, the bound clearly holds. □

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