On the Price of Privacy for Language Identification and Generation

• URL: http://arxiv.org/abs/2604.07238v1
• Date: Wed, 08 Apr 2026 16:04:16 GMT
• Title: On the Price of Privacy for Language Identification and Generation
• Abstract summary: We study the cost of privacy in language learning by studying differentially private (DP) language identification and generation.<n>Our results show that the cost of privacy in language learning is surprisingly mild: absent entirely under approximate DP, and exactly a $min1,varepsilon$ factor in the exponent under pure DP.
• Score: 39.91890433860882
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $(\varepsilon, δ)$-DP with constant $\varepsilon > 0$ recovers the non-private error rates: $\exp(-r(n))$ for identification (for any $r(n) = o(n)$) and $\exp(-Ω(n))$ for generation. Under pure $\varepsilon$-DP, the exponents degrade by a multiplicative factor of $\min\{1, \varepsilon\}$, which we show is tight up to constants. Notably, for generation under pure DP with mild assumptions, the upper bound $\exp(-\min\{1,\varepsilon\} \cdot Ω(n))$ 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,\varepsilon\}$ factor in the exponent under pure DP.

Related papers

• Space-Efficient Language Generation in the Limit [34.38365460078856]
  We propose a resource-aware theory of textit generation in the limit under the minimal constraint of space efficiency.<n>We focus on $mathcalC_s,k$, the collection of languages recognized by DFAs with at most $s$ states over an alphabet of size $k$.<n>Under a stricter memory budget, we characterize the strongest possible generation guarantees.
  arXiv  Detail & Related papers  (2026-06-24T12:55:34Z)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  We propose a piecewise stationary linear bandit (PSLB) model where the quality of an arm is measured by its return averaged over all contexts. PS$varepsilon$BAI$+$ is guaranteed to identify an $varepsilon$-optimal arm with probability $ge 1-delta$ and with a minimal number of samples.
  arXiv  Detail & Related papers  (2024-10-10T06:15:42Z)
• Private Mean Estimation with Person-Level Differential Privacy [6.621676316292624]
  We study person-level differentially private mean estimation in the case where each person holds multiple samples. We give computationally efficient algorithms under approximate-DP and computationally inefficient algorithms under pure DP, and our nearly matching lower bounds hold for the most permissive case of approximate DP.
  arXiv  Detail & Related papers  (2024-05-30T18:20:35Z)
• Smooth Sensitivity for Geo-Privacy [17.835910182900985]
  Local model of differential privacy (LDP) is the predominant model under which the problem has been studied. Geo-Privacy (GP) stipulates that the level of distinguishability be proportional to $mathrmdist(x_i, x_i')$. We generalize the smooth sensitivity framework from Differential Privacy to Geo-Privacy, which allows us to add noise tailored to the hardness of the given instance.
  arXiv  Detail & Related papers  (2024-05-10T08:32:07Z)
• Near-Optimal Differentially Private Reinforcement Learning [16.871660060209674]
  We study online exploration in reinforcement learning with differential privacy constraints. Existing work established that no-regret learning is possible under joint differential privacy (JDP) and local differential privacy (LDP) We design an $epsilon$-JDP algorithm with a regret of $widetildeO(sqrtSAH2T+S2AH3/epsilon)$ which matches the information-theoretic lower bound of non-private learning.
  arXiv  Detail & Related papers  (2022-12-09T06:03:02Z)
• 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)
• Differentially Private Exploration in Reinforcement Learning with Linear Representation [102.17246636801649]
  We first consider the setting of linear-mixture MDPs (Ayoub et al., 2020) (a.k.a. model-based setting) and provide an unified framework for analyzing joint and local differential private (DP) exploration. We further study privacy-preserving exploration in linear MDPs (Jin et al., 2020) (a.k.a. model-free setting) where we provide a $widetildeO(sqrtK/epsilon)$ regret bound for $(epsilon,delta)
  arXiv  Detail & Related papers  (2021-12-02T19:59:50Z)
• Locally Differentially Private Reinforcement Learning for Linear Mixture Markov Decision Processes [78.27542864367821]
  Reinforcement learning (RL) algorithms can be used to provide personalized services, which rely on users' private and sensitive data. To protect the users' privacy, privacy-preserving RL algorithms are in demand. We propose a novel $(varepsilon, delta)$-LDP algorithm for learning a class of Markov decision processes (MDPs) dubbed linear mixture MDPs.
  arXiv  Detail & Related papers  (2021-10-19T17:44:09Z)
• Differential Privacy in Personalized Pricing with Nonparametric Demand Models [15.036147440342338]
  This paper studies a dynamic personalized pricing problem with textitunknown nonparametric demand models under data privacy protection. Two concepts of data privacy, which have been widely applied in practices, are introduced. We develop two algorithms which make pricing decisions and learn the unknown demand on the fly, while satisfying the CDP and LDP gurantees respectively.
  arXiv  Detail & Related papers  (2021-09-10T01:56:55Z)
• Learning with User-Level Privacy [61.62978104304273]
  We analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samples, user-level DP protects a user's entire contribution. We derive an algorithm that privately answers a sequence of $K$ adaptively chosen queries with privacy cost proportional to $tau$, and apply it to solve the learning tasks we consider.
  arXiv  Detail & Related papers  (2021-02-23T18:25:13Z)

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.