On the Price of Privacy for Language Identification and Generation¶

会议: NeurIPS 2026
arXiv: 2604.07238
OpenReview: https://openreview.net/forum?id=tuVOBgviZm
领域: 安全
关键词: 差分隐私, 语言识别, 语言生成, 隐私代价, 统计学习理论

一句话总结¶

首次系统建立了不可知统计语言学习（识别与生成）的差分隐私理论框架，证明在近似差分隐私下隐私成本为零，而在纯差分隐私下收敛指数仅损失 $\min\{1, \varepsilon\}$ 因子且紧致匹配下界。

研究背景与动机¶

在大语言模型（LLM）日益依赖医疗、金融及个人日常对话等敏感私有数据进行预训练与对齐微调的背景下，差分隐私（Differential Privacy, DP）已成为保障数据安全和防止训练数据记忆泄露的标准数学工具。在工程实践中，DP-SGD微调语言模型展现出了逼近非隐私基线的优异经验性能，表明语言建模对差分隐私噪声具有出人意料的鲁棒性。然而，这种良好表现背后究竟是工程调优的偶然现象，还是源自语言学习任务内在的数学结构？现有统计学习与PAC学习理论虽对有限假设类或高斯分布估计的隐私开销给出了经典刻画，但针对可数无限语言类的语言识别与生成任务，其根本的理论隐私代价（Price of Privacy）此前仍完全处于空白状态。

将差分隐私引入统计语言学习面临着独特的算法与敏感度壁垒。非隐私设定下（如 Høgsgaard & Pabbaraju 2026 的不可知统计框架），语言识别依赖经验风险边际截断测试，这种选择准则是高度不连续的——单条样本的变动即可瞬间打破边际条件，导致离散决策发生翻转；而在语言生成中，非隐私算法依赖针对各语言未见词项的指针前进机制，单个样本的缺失可能使指针发生任意距离的回退，其敏感度无界。直接应用传统私有化机制要么导致噪声过大使得界失效，要么完全无法满足差分隐私的局部 Lipschitz 约束。

为了破解这一理论困境，本文选择从目标函数的敏感度重构切入：语言学习的目标并非直接拟合经验分布，而是可以通过构造平滑赤字惩罚函数与有界前缀计数器，将识别与生成任务的敏感度分别收敛到可控的多项式尺度与常数尺度。核心 idea：通过将不连续边际测试松弛为平滑赤字评分函数、将无界指针重构为常数敏感度的阈值化前缀计数器，结合指数机制与高斯机制给出最优私有化算法，并利用群隐私耦合下界精确证明：近似 DP 下语言识别与生成的隐私成本为零，而纯 DP 下收敛速率的指数退化因子严格等于 $\min\{1, \varepsilon\}$。

方法详解¶

整体框架¶

在不可知统计语言学习设定中，学习算法观测由未知分布 $\mathcal{D}$ 在可数词表 $\mathcal{U}$ 上独立同分布采样的 $n$ 个样本 $S=(x_1, \dots, x_n) \sim \mathcal{D}^n$。给定可数语言集合 $\mathcal{C} = \{L_1, L_2, \dots\}$（每个 $L_i \subseteq \mathcal{U}$ 为无限集合），系统针对两类不同目标分别设计端到端差分隐私算法： 1. 私有语言识别（Private Identification）：输出语言索引 $\widehat{i} \in [f(n)]$，使得总体风险 $\mathrm{err}_{\mathcal{D}}(L_{\widehat{i}}) = \Pr_{x \sim \mathcal{D}}[x \notin L_{\widehat{i}}]$ 逼近最优总体风险 $\inf_{L \in \mathcal{C}} \mathrm{err}_{\mathcal{D}}(L)$。 2. 私有语言生成（Private Generation）：在有限见证索引假设下输出一个既有效又新颖的字符串 $\widehat{x} \in \mathcal{U}$，满足 $\widehat{x} \in \mathrm{supp}(\mathcal{D}) \setminus S$。

整体私有化算法流水线包括经验量统计、平滑赤字评分构建、隐私选择机制采样以及后处理生成四个核心阶段。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["私有样本输入 S ~ D^n 与可数语言族 C"] --> B["平滑赤字评分机制<br/>计算经验边际 M_S(i) 与赤字 d_S(i)"]
    B --> C["阈值化前缀计数与常数敏感度重构<br/>统计前缀频数 a_i^W(S) 并构造 q_W(S,i)"]
    C --> D["联合搜索与双机制私有化<br/>扩展积空间搜索 (i,t) 并经由指数/高斯机制私有化"]
    D --> E["两阶段无碰撞生成与识别结果输出<br/>输出识别语言 L_hat 或从尾部随机采样全新合法字符串 x_hat"]

关键设计¶

1. 平滑赤字评分机制：消除语言识别中的硬边际不连续性

非隐私语言识别在递增搜索视界 $[f(n)]$ 内寻找满足边际条件 $\mathrm{err}_S(L_j) - \mathrm{err}_S(L_i) > 2/f(n)$（对所有 $j < i$）的最大索引 $i$。单样本替换会导致边际指示函数发生 $0/1$ 跳变，敏感度达到 $1$ 且不可微。为此，本文设计了连续且具有局部 Lipschitz 性质的软边际赤字函数。首先定义经验边际： $$M_S(i) := \begin{cases} 1, & i=1 \\ \min_{j \in [i-1]} (\mathrm{err}_S(L_j) - \mathrm{err}_S(L_i)), & i \geq 2 \end{cases}$$ 进而定义边际赤字 $d_S(i) := \bigl(\frac{2}{f(n)} - M_S(i)\bigr)_+$ 与复合评分函数： $$q(S, i) := i - f(n)^2 d_S(i)$$ 该设计的精妙之处在于：线性项 $i$ 奖励更大的语言索引，以保证覆盖真实最优语言 $i^\star$；惩罚项 $-f(n)^2 d_S(i)$ 则对未满足边际测试的索引进行强力压制。当数据集变动一个样本时，经验风险变动至多 $1/n$，由逐点最小值保持 Lipschitz 性可得 $|M_S(i) - M_{S'}(i)| \leq 2/n$，因此赤字变化至多 $2/n$，使得整体评分函数的灵敏度严格控制在 $\Delta q \leq 2f(n)^2/n$。在集中事件 $\mathcal{E}$ 下，$i^\star$ 处的赤字严格为 0，而其余任一 $i \neq i^\star$ 的评分至多为 $i^\star - 1$，保证了至少为 $1$ 的确定性评分间隙。

2. 阈值化前缀计数与常数敏感度重构：打破语言生成无界指针瓶颈

非隐私语言生成的经典算法对每个候选语言维护指向其首个未见字符串的指针，并选取指针前移最远的语言。若某字符串在数据集中仅出现一次，其缺失将导致该指针瞬间回退数百甚至无限步，灵敏度无界。本文提出通过「阈值化前缀计数」替代指针机制。给定见证窗口 $W \geq i(\mathcal{C}, \mathcal{D})$，定义语言 $L_i$ 在窗口内的索引子集 $I_i(W) := \{k \in [W] : u_k \in L_i\}$，并统计其最小前缀频数： $$a_i^W(S) := \begin{cases} \min_{k \in I_i(W)} N_S(u_k), & I_i(W) \neq \emptyset \\ n, & I_i(W) = \emptyset \end{cases}$$ 其中 $N_S(u_k) := \sum_{t=1}^n \mathbf{1}\{x_t = u_k\}$ 为出现频次。随后引入频数阈值 $g(n) \to \infty$（如 $g(n) = \lfloor n p_W^\star / 2 \rfloor$），构建生成赤字 $d_i^W(S) := (g(n) - a_i^W(S))_+$ 及评分： $$q_W(S, i) := -d_i^W(S)$$ 由于每条样本仅能使单个元素频数变化 $\pm 1$，取最小值与截断均保持 1-Lipschitz，该评分的全局敏感度严格为 $\Delta = 1$，完全独立于样本数 $n$ 与视界 $f(n)$。对真实包含于数据支撑集的参考语言 $L_{i^\star}$，在 Chernoff 界下其所有前缀频次均超过 $g(n)$，评分达到最大值 $0$；而对于包含外部见证词的错误语言，其见证词永远不会被采样（频数为 0），评分为 $-g(n)$。常数敏感度 $\Delta=1$ 与线性增长的评分间隙 $\Omega(n)$ 相结合，使得指数机制能够实现全指数级的收敛速率。

3. 联合搜索与双机制私有化：消除先验依赖并实现自由近似隐私

当见证窗口 $W$ 的先验上界未知时，本文进一步将状态空间扩展为语言索引与见证阈值的二维积空间 $(i, t) \in [f(n)] \times [h(n)]$，构建联合双重评分： $$q_{\mathrm{pair}}(S, (i, t)) := t - \frac{h(n)}{g(n)} d_{i, t}(S)$$ 此时评分敏感度为 $h(n)/g(n)$，而评分间隙同步缩放为 $\Omega(h(n))$，有效信噪比仍维持在 $g(n)$ 阶，成功解耦了对公共窗口参数的依赖。在此基础上，论文针对纯 DP 与近似 DP 分别推导了最优机制映射： - 纯 $\varepsilon$-DP：采用指数机制 $\mathrm{EM}_\varepsilon(S, q, \mathcal{R})$，输出概率正比于 $\exp\bigl(\frac{\varepsilon}{2\Delta} q(S, \cdot)\bigr)$。在生成任务中，选择出正确支撑语言后，利用与私有数据独立的均匀随机性 $j \sim \mathrm{Unif}([2^n])$ 从该语言超出窗口的候选集中挑选第 $j$ 小元素，利用鸽巢原理保证与已有训练集的碰撞概率不超过 $n/2^n \leq \exp(-n/2)$。 - 近似 $(\varepsilon, \delta)$-DP：采用高斯机制对向量化评分添加方差为 $\sigma^2 = \Theta\bigl(\frac{\Delta_2^2 \log(1/\delta)}{\varepsilon^2}\bigr)$ 的噪声，再执行确定性 argmax。由于生成评分向量具有极小的 $\ell_2$ 敏感度，高斯扰动量远小于 $\Omega(n)$ 的评分间隙，使得近似 DP 彻底消除了纯 DP 中的 $\varepsilon$ 退化因子，实现了无隐私代价恢复。

4. 两阶段无碰撞生成与识别结果输出：消除已有样本记忆泄露

私有化机制完成语言或联合对的提取后，必须确保生成字符串不仅落于有效真实支撑集 $\mathrm{supp}(\mathcal{D})$ 内，而且绝不与包含敏感信息的训练样本集 $S$ 发生重叠（即满足新颖性 Novelty 要求 $\widehat{x} \notin S$）。为此，算法采用两阶段后处理策略：首先利用指数机制或高斯机制输出私有语言索引 $\widehat{i}$ 或阈值 $\widehat{t}$；随后脱离私有样本，直接利用外部公共独立均匀随机源 $\widehat{j} \sim \mathrm{Unif}([2^n])$，在候选语言超出见证截断的无限后缀子集 $L_{\widehat{i}} \cap \{u_{\widehat{t}+1}, u_{\widehat{t}+2}, \dots\}$ 的前 $2^n$ 个元素中抽取输出。由于候选语言为无限集且被前序步骤证明包含于真实支撑集，集合中至多只有 $n$ 个元素可能与训练样本 $S$ 相同。因此采样发生碰撞的失效概率被严密控制在 $n/2^n \le \exp(-n/2)$ 以内，且根据差分隐私的后处理不变性，这一步引入的公共随机性完全不耗费额外的隐私预算。

损失函数 / 训练策略¶

作为纯理论框架，本算法不涉及反向传播与梯度下降训练，其核心计算步骤由有限离散集合上的差分隐私扰动与采样策略构成。具体超参数与阈值选取准则如下： 1. 视界截断函数：对于语言识别，设定 $f(n) = \sqrt{c \log n}$（其中 $c > 0$ 充分大）以保证最优语言 $i^\star \leq f(n)$ 且边际阈值 $2/f(n) < c_{\mathrm{gap}}$；或者选取任意增长序列满足 $f(n) \to \infty$ 且 $f(n) = o(\sqrt{n})$。 2. 频数截断门限：对于语言生成，在已知支撑集最小质量下界 $p_0 \leq \min_{k} \Pr[x = u_k]$ 时，取 $g(n) = \lfloor n p_0 / 2 \rfloor$；在未经验证的任意可数场景下，取任意次线性增长阶 $g(n) = \lfloor r(n) \rfloor$（$r(n) = o(n)$）。 3. 输出采样池容量：新颖性保障池选取容量为 $2^n$ 的尾部集合 $L_{\widehat{i}} \cap \{u_{W+1}, u_{W+2}, \dots\}$，结合完全独立于样本集的公钥随机数 $j \sim \mathrm{Unif}([2^n])$ 进行后处理输出，天然满足差分隐私后处理不变性。

实验关键数据¶

主实验¶

论文通过信息论方法严格推导了各学习任务在不同隐私机制下的最优误差上界（Upper Bound, UB）与基于群隐私耦合构造的紧致下界（Lower Bound, LB）。表 1 总结了识别超额风险 $\mathrm{IdErr}$ 与生成失效率 $\mathrm{GenErr}$ 的渐近收敛阶。

任务类型	理论边界类型	非隐私基线 (Høgsgaard 2026)	纯 $\varepsilon$-DP (本文)	近似 $(\varepsilon, \delta)$-DP (本文)	隐私代价评价
语言识别 (Identification)	误差上界 (UB)	$\exp(-r(n)), \forall r(n)=o(n)$	$\exp(-\min\{1, \varepsilon\} \cdot r(n))$	$\exp(-r(n))$	近似DP完全无损；纯DP指数缩放 $\min\{1,\varepsilon\}$
语言识别 (Identification)	理论下界 (LB)	$\exp(-O(n))$	$\exp(-\min\{1, \varepsilon\} \cdot O(n))$	$\exp(-O(n))$	证明了 $\min\{1, \varepsilon\}$ 因子在指数上的紧致性
语言生成 (Generation)	误差上界 (UB)	$\exp(-\Omega(n))$	$\exp(-\min\{1, \varepsilon\} \cdot \Omega(n))$	$\exp(-\Omega(n))$	达成纯指数收敛，常数敏感度消除视界惩罚
语言生成 (Generation)	理论下界 (LB)	$\exp(-O(n))$	$\exp(-\min\{1, \varepsilon\} \cdot O(n))$	$\exp(-O(n))$	上下界在指数阶上严格匹配，达到信息论最优速率

消融实验¶

表 2 对比了算法在不同先验信息、视界函数 $f(n)$ 增长速度、见证窗口认知程度以及隐私预算 $\varepsilon$ 极端区间下的收敛表现与敏感度消融。

实验/理论配置	敏感度特性	先验假设要求	误差收敛速率 (纯 $\varepsilon$-DP)	机制主导误差项	说明
识别：对数视界 $f(n)=\sqrt{c\log n}$	$\Theta(\log n / n)$	可达最优假设 ($i^\star < \infty$)	$\exp\bigl(-\min\{1, \varepsilon\} \cdot \frac{n}{\log n}\bigr)$	统计项与隐私项平衡	最优选择，误差达到 $\exp(-\min\{1,\varepsilon\}\widetilde{\Omega}(n))$
识别：多项式视界 $f(n)=n^\alpha (\alpha<0.5)$	$\Theta(n^{2\alpha - 1})$	可达最优假设 ($i^\star < \infty$)	$\exp\bigl(-\min\{1, \varepsilon\} \cdot n^{1-2\alpha}\bigr)$	敏感度随视界增大而恶化	验证了敏感度 $\Delta q = \Theta(f(n)^2/n)$ 的理论惩罚
生成：已知见证界与质量下界 $p_0$	$\Delta = 1$ (常数)	见证界 $W < \infty, p_0 \leq p_W^\star$	$\exp(-\min\{1, \varepsilon\} \cdot \Omega(n))$	隐私选择项 $f(n)\exp(-\frac{\varepsilon n p_0}{8})$	达到全线性指数，与非隐私基线速率同构
生成：未知见证界但知质量下界	$\Delta = h(n)/g(n)$	仅需存在参考语言与有限见证	$\exp(-\min\{1, \varepsilon\} \cdot \Omega(n))$	联合搜索前缀积 $f(n)h(n)$ 预因子	搜索空间变大，但不影响主指数阶
生成：无任何先验下界 ($p_0$ 未知)	$\Delta = 1$	仅需通用不可知条件	$\exp(-\varepsilon \cdot r(n)), \forall r(n)=o(n)$	覆盖项要求截断降阶	速率退化为次指数，与非隐私次指数相当
极限工况：强隐私区 ($\varepsilon \ll 1$)	保持对应机制	任意前述基准配置	纯 DP: $\exp(-\varepsilon \cdot \cdot)$ vs 近似 DP: $\exp(-\varepsilon^2 \cdot \cdot)$	机制方差主导	表明在超低隐私预算下纯 DP 机制理论上反而优于高斯机制

关键发现¶

近似 DP 的免费定理（Free Privacy）：对于 identification 与 generation 两大任务，只要松弛到高斯机制的 $(\varepsilon, \delta)$-DP，只要 $\varepsilon = \Omega(1)$ 且 $\delta \geq \exp(-\mathrm{poly}(n))$，隐私噪声带来的扰动概率均以远超统计项的速度衰减，非隐私状态下的最优指数收敛率完全得以无损复现。
纯 DP 的精确指数衰减律：在纯 $\varepsilon$-DP 限制下，两类任务均遭遇了严格的速率瓶颈，其收敛指数必然乘上一个紧致的乘性因子 $\min\{1, \varepsilon\}$。当 $\varepsilon \geq 1$ 时隐私开销消失；当 $\varepsilon < 1$ 时，群隐私耦合引理证明了任何差分隐私算法都无法绕过 $\varepsilon$ 的线性折减。
任务间敏感度结构的本源差异：语言生成之所以能够取得比语言识别更强的全指数收敛率（$\exp(-\Omega(n))$ 对比 $\exp(-o(n))$），核心在于生成任务本质上只需要在候选集中识别出一个「良好且支撑充分」的语言，其设计出的阈值化前缀统计量拥有常数敏感度（$\Delta=1$）；而识别任务必须从全体候选中精准锁定唯一的经验最优者，其边际比较强制引入了随视界增长的全局敏感度 $\Theta(f(n)^2/n)$。

亮点与洞察¶

敏感度几何重构范式：将传统具有阶跃不连续性或无界敏感度的组合逻辑（如边际判断、前缀指针），通过添加单边截断惩罚项（Deficit Penalty）重塑为低敏感度或常数敏感度的光滑势能函数。这种设计思路可直接复用到任何带有离散约束的模型选择与受限采样算法的私有化改造中。
群隐私耦合分析技巧：下界证明没有走传统的 Fano 不等式或 Assouad 局部引理，而是巧妙结合了多维分布间的同概率耦合与群隐私放大效应（Lemma 5.2）。针对生成任务的构造极具创新性——通过设计共享高概率核心基底但具有完全不相交私有尾部的非对称分布对，迫使满足纯差分隐私的算法在任一分布下都有不可压缩的失败概率。
对现代 LLM 差分隐私微调的理论注脚：该论文在统计学习层面上为「为什么 DP 微调大语言模型损失极小」给出了第一个有力的数学解释——在近似差分隐私下，只要支持生成的目标空间具有良好的冗余度与前缀可分性，统计误差就占据绝对主导地位，隐私代价在渐近意义下确实可以趋近于零。

局限与展望¶

计算复杂度与可数枚举假设：当前算法基于对语言集合 $\mathcal{C}$ 和词表 $\mathcal{U}$ 的显式截断枚举，属于纯信息论意义下的存在性证明，并未提供多项式时间内的计算效率保证，尚无法直接作为实用算法替代工业界基于梯度裁剪的 DP-SGD 流程。
独立同分布与样本级隐私限制：理论分析均建立在样本从未知分布独立同分布采样的不可知统计框架下，未考虑序列内部 token 间的长程依赖以及 Gold 经典的对抗式在线流式序列场景；同时保护粒度为单个字符串，未拓展到单个用户贡献整套长文档的用户级隐私（User-level DP）。
未来方向：将理论扩展至带安全性或对齐约束（如防御有害语言生成）的有偏生成目标；探索多项式时间图灵机可判别语言类上的计算高效 DP 语言生成算法。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统建立统计语言学习的差分隐私理论框架，填补了语言学习理论与差分隐私交互的核心空白。
实验充分度: ⭐⭐⭐⭐⭐ 纯理论证明极其严谨扎实，给出了识别与生成在纯DP及近似DP下的完整上下界闭环匹配。
写作质量: ⭐⭐⭐⭐⭐ 动机陈述极具启发性，算法设计层层递进，敏感度消除的核心技术解释非常直观透彻。
价值: ⭐⭐⭐⭐⭐ 为大语言模型隐私微调优异表现提供了深刻的统计物理学与信息论解释，极具理论奠基意义。

任务类型	理论边界类型	非隐私基线 (Høgsgaard 2026)	纯 \(\varepsilon\)-DP (本文)	近似 \((\varepsilon, \delta)\)-DP (本文)	隐私代价评价
语言识别 (Identification)	误差上界 (UB)	\(\exp(-r(n)), \forall r(n)=o(n)\)	\(\exp(-\min\{1, \varepsilon\} \cdot r(n))\)	\(\exp(-r(n))\)	近似DP完全无损；纯DP指数缩放 \(\min\{1,\varepsilon\}\)
语言识别 (Identification)	理论下界 (LB)	\(\exp(-O(n))\)	\(\exp(-\min\{1, \varepsilon\} \cdot O(n))\)	\(\exp(-O(n))\)	证明了 \(\min\{1, \varepsilon\}\) 因子在指数上的紧致性
语言生成 (Generation)	误差上界 (UB)	\(\exp(-\Omega(n))\)	\(\exp(-\min\{1, \varepsilon\} \cdot \Omega(n))\)	\(\exp(-\Omega(n))\)	达成纯指数收敛，常数敏感度消除视界惩罚
语言生成 (Generation)	理论下界 (LB)	\(\exp(-O(n))\)	\(\exp(-\min\{1, \varepsilon\} \cdot O(n))\)	\(\exp(-O(n))\)	上下界在指数阶上严格匹配，达到信息论最优速率

实验/理论配置	敏感度特性	先验假设要求	误差收敛速率 (纯 \(\varepsilon\)-DP)	机制主导误差项	说明
识别：对数视界 \(f(n)=\sqrt{c\log n}\)	\(\Theta(\log n / n)\)	可达最优假设 (\(i^\star < \infty\))	\(\exp\bigl(-\min\{1, \varepsilon\} \cdot \frac{n}{\log n}\bigr)\)	统计项与隐私项平衡	最优选择，误差达到 \(\exp(-\min\{1,\varepsilon\}\widetilde{\Omega}(n))\)
识别：多项式视界 \(f(n)=n^\alpha (\alpha<0.5)\)	\(\Theta(n^{2\alpha - 1})\)	可达最优假设 (\(i^\star < \infty\))	\(\exp\bigl(-\min\{1, \varepsilon\} \cdot n^{1-2\alpha}\bigr)\)	敏感度随视界增大而恶化	验证了敏感度 \(\Delta q = \Theta(f(n)^2/n)\) 的理论惩罚
生成：已知见证界与质量下界 \(p_0\)	\(\Delta = 1\) (常数)	见证界 \(W < \infty, p_0 \leq p_W^\star\)	\(\exp(-\min\{1, \varepsilon\} \cdot \Omega(n))\)	隐私选择项 \(f(n)\exp(-\frac{\varepsilon n p_0}{8})\)	达到全线性指数，与非隐私基线速率同构
生成：未知见证界但知质量下界	\(\Delta = h(n)/g(n)\)	仅需存在参考语言与有限见证	\(\exp(-\min\{1, \varepsilon\} \cdot \Omega(n))\)	联合搜索前缀积 \(f(n)h(n)\) 预因子	搜索空间变大，但不影响主指数阶
生成：无任何先验下界 (\(p_0\) 未知)	\(\Delta = 1\)	仅需通用不可知条件	\(\exp(-\varepsilon \cdot r(n)), \forall r(n)=o(n)\)	覆盖项要求截断降阶	速率退化为次指数，与非隐私次指数相当
极限工况：强隐私区 (\(\varepsilon \ll 1\))	保持对应机制	任意前述基准配置	纯 DP: \(\exp(-\varepsilon \cdot \cdot)\) vs 近似 DP: \(\exp(-\varepsilon^2 \cdot \cdot)\)	机制方差主导	表明在超低隐私预算下纯 DP 机制理论上反而优于高斯机制