Differentially Private Language Generation and Identification in the Limit

• URL: http://arxiv.org/abs/2604.08504v1
• Date: Thu, 09 Apr 2026 17:48:46 GMT
• Title: Differentially Private Language Generation and Identification in the Limit
• Abstract summary: We study the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan [KM24], under the constraint of differential privacy.<n>We provide an $varepsilon$-differentially-private algorithm that generates in the limit from any countable collection.<n>We prove that no $varepsilon$-DP algorithm can identify a collection containing two languages with an infinite intersection and a finite set difference.
• Score: 17.31852533022177
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We initiate the study of language generation in the limit, a model recently introduced by Kleinberg and Mullainathan [KM24], under the constraint of differential privacy. We consider the continual release model, where a generator must eventually output a stream of valid strings while protecting the privacy of the entire input sequence. Our first main result is that for countable collections of languages, privacy comes at no qualitative cost: we provide an $\varepsilon$-differentially-private algorithm that generates in the limit from any countable collection. This stands in contrast to many learning settings where privacy renders learnability impossible. However, privacy does impose a quantitative cost: there are finite collections of size $k$ for which uniform private generation requires $Ω(k/\varepsilon)$ samples, whereas just one sample suffices non-privately. We then turn to the harder problem of language identification in the limit. Here, we show that privacy creates fundamental barriers. We prove that no $\varepsilon$-DP algorithm can identify a collection containing two languages with an infinite intersection and a finite set difference, a condition far stronger than the classical non-private characterization of identification. Next, we turn to the stochastic setting where the sample strings are sampled i.i.d. from a distribution (instead of being generated by an adversary). Here, we show that private identification is possible if and only if the collection is identifiable in the adversarial model. Together, our results establish new dimensions along which generation and identification differ and, for identification, a separation between adversarial and stochastic settings induced by privacy constraints.

Related papers

• Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
  This paper introduces a novel proof technique based on a multi-player communication game.<n>We show that winning this communication game requires transmitting information proportional to the number of over-active users.<n>We show that this communication-theoretic technique generalizes to broad classes of problems, yielding lower bounds for private medians, quantiles, and max-select.
  arXiv  Detail & Related papers  (2026-02-12T17:49:07Z)
• High-Dimensional Asymptotics of Differentially Private PCA [4.168157981135696]
  In differential privacy, statistics of a sensitive dataset are privatized by introducing random noise.<n>It remains unclear if such high noise levels are truly necessary or a limitation of the proof techniques.<n>This paper explores whether we can obtain sharp privacy characterizations that identify the smallest noise level required to achieve a target privacy level.
  arXiv  Detail & Related papers  (2025-11-10T16:17:16Z)
• DP-Fusion: Token-Level Differentially Private Inference for Large Language Models [51.71591819896191]
  Large language models (LLMs) do not preserve privacy at inference-time.<n> DP-Fusion provably bounds the influence a set of tokens in the context can have on the LLM's output.<n>We show that our method creates token-level provably privatized documents with substantially improved theoretical and empirical privacy.
  arXiv  Detail & Related papers  (2025-07-06T20:49:39Z)
• InvisibleInk: High-Utility and Low-Cost Text Generation with Differential Privacy [7.006059299522521]
  InvisibleInk is a scalable long-form text generation framework satisfying rigorous differential privacy guarantees.<n>We reduce the privacy cost by isolating and clipping only the sensitive information in the model logits.<n>We improve text quality by sampling from a small superset of the top-$k$ private tokens.
  arXiv  Detail & Related papers  (2025-06-30T18:00:41Z)
• Privacy Amplification via Shuffling: Unified, Simplified, and Tightened [20.10078781197001]
  We propose a comprehensive framework for privacy amplification in both single-message and multi-message shuffle protocols. Our theoretical results demonstrate that our framework provides tighter bounds, especially for local randomizers with extremal probability design. Our bounds also result in a remarkably efficient $tildeO(n)$ algorithm that numerically amplifies privacy in less than $10$ seconds for $n=108$ users.
  arXiv  Detail & Related papers  (2023-04-11T06:27:25Z)
• On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
  We study the space complexity of the two related fields of differential privacy and adaptive data analysis. We show that there exists a problem P that requires exponentially more space to be solved efficiently with differential privacy. The line of work on adaptive data analysis focuses on understanding the number of samples needed for answering a sequence of adaptive queries.
  arXiv  Detail & Related papers  (2023-02-11T14:45:31Z)
• Analyzing Privacy Leakage in Machine Learning via Multiple Hypothesis Testing: A Lesson From Fano [83.5933307263932]
  We study data reconstruction attacks for discrete data and analyze it under the framework of hypothesis testing. We show that if the underlying private data takes values from a set of size $M$, then the target privacy parameter $epsilon$ can be $O(log M)$ before the adversary gains significant inferential power.
  arXiv  Detail & Related papers  (2022-10-24T23:50:12Z)
• On the Statistical Complexity of Estimation and Testing under Privacy Constraints [17.04261371990489]
  We show how to characterize the power of a statistical test under differential privacy in a plug-and-play fashion. We show that maintaining privacy results in a noticeable reduction in performance only when the level of privacy protection is very high. Finally, we demonstrate that the DP-SGLD algorithm, a private convex solver, can be employed for maximum likelihood estimation with a high degree of confidence.
  arXiv  Detail & Related papers  (2022-10-05T12:55:53Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• Quantifying identifiability to choose and audit $\epsilon$ in differentially private deep learning [15.294433619347082]
  To use differential privacy in machine learning, data scientists must choose privacy parameters $(epsilon,delta)$. We transform $(epsilon,delta)$ to a bound on the Bayesian posterior belief of the adversary assumed by differential privacy concerning the presence of any record in the training dataset. We formulate an implementation of this differential privacy adversary that allows data scientists to audit model training and compute empirical identifiability scores and empirical $(epsilon,delta)$.
  arXiv  Detail & Related papers  (2021-03-04T09:35:58Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  We show that random shuffling amplifies differential privacy guarantees of locally randomized data. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees.
  arXiv  Detail & Related papers  (2020-12-23T17:07:26Z)
• Successive Refinement of Privacy [38.20887036580742]
  This work examines how much randomness is needed to achieve local differential privacy (LDP) A motivating scenario is providing multiple levels of privacy to multiple analysts, either for distribution or for heavy-hitter estimation. We show that we cannot reuse random keys over time while preserving privacy of each user.
  arXiv  Detail & Related papers  (2020-05-24T04:16:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.