arXiv:2604.08504stat.MLcs.AI2026-04被引 4

在差分隐私约束下研究语言生成与识别的极限,揭示了隐私带来的本质差异。

Differentially Private Language Generation and Identification in the Limit

  • 提出可在任意可数语言集合上实现差分隐私生成的算法
  • 私有生成需Ω(k/ε)样本,非私有仅需1个样本
  • 隐私使识别存在根本障碍,尤其在对抗性设定中

我们首次在差分隐私约束下研究由Kleinberg和Mullainathan [KM24]提出的语言生成极限模型。考虑持续释放模型,生成器需最终输出一系列有效字符串,并保护整个输入序列的隐私。对于可数语言集合,隐私不带来定性代价:我们给出一个ε-差分私有算法,可从任意可数语言集合生成。然而,隐私带来定量代价:存在大小为k的有限语言集合,其均匀私有生成需Ω(k/ε)样本,而非私有情形仅需1个样本。随后转向更难的语言识别问题。我们证明:任何ε-差分私有算法都无法识别包含两个具有无限交集但有限差集的语言集合,该条件远强于经典非私有识别特征。在独立同分布采样设定下,私有识别可行当且仅当该集合在对抗模型下可识别。我们的结果确立了生成与识别之间的新维度差异,并揭示了隐私导致对抗性与随机性设定间的分离。

原文摘要 · Abstract (English)

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.

语言生成差分隐私识别理论

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。