技术摘要：个性化差分隐私预算的局限性

问题陈述

在差分隐私（DP）中，选择合适的隐私预算（$\epsilon$）是一个根本性挑战：较小的 $\epsilon$ 能确保更强的隐私，但会降低计算的效用（准确性）。虽然经典 DP 对所有参与者施加统一的预算，但一种自然的扩展是个性化（或异构）DP，其中每个智能体 $i$ 具有不同的隐私需求 $\epsilon_i$。这种方法的动机在于，智能体具有不同的隐私态度，且个性化在理论上扩展了可行算法的空间，从而可能改善隐私与准确性的权衡。

然而，完全个性化的机制（例如基于个体 $\epsilon_i$ 对数据点进行重新加权的仿射估计量）难以审计、沟通和适应。一种更简单的替代方案是阈值估计量，它丢弃隐私要求过于严格的数据点，并对剩余数据应用单一且精心选择的隐私预算。

本文解决的核心问题是：与简单的阈值基线相比，完全个性化的复杂性是否能带来显著的效用提升（具体针对均值估计）？ 作者调查了完全个性化的“边际价值”是否显著，或者在大多数实际情形中收益是否有限。

方法论与模型

作者关注的是在给定 $n$ 个独立同分布（i.i.d.）数据点且每个点 $x_i$ 具有特定隐私预算 $\epsilon_i$ 的情况下，对支撑集有界 $[-1/2, 1/2]$ 的分布 $P$ 进行均值估计的问题。

比较的估计量

1. 最优仿射估计量（完全个性化）：

   • 这是异构 DP 中已知的最佳估计量。它使用数据点的加权平均：$\hat{\mu} = \sum w_i x_i + Z$，其中 $Z$ 是拉普拉斯噪声。
   • 权重 $w_i$ 经过优化以最小化均方误差（MSE）。
   • 最优策略涉及“截断”隐私水平：选择一个阈值 $\tau$，并将有效隐私水平设置为 $\bar{\epsilon}_i = \min(\epsilon_i, \tau)$。权重与这些截断后的水平成正比（$w_i \propto \bar{\epsilon}_i$），噪声尺度由相对于截断预算的最大灵敏度决定。
   • MSE 表征为：
     $$\text{MSE}_{\text{aff}}(\epsilon) = \inf_{\tau>0} \left( \frac{q_\tau}{4s_\tau^2} + \frac{2}{s_\tau^2} \right)$$
     其中 $s_\tau = \sum \min(\epsilon_i, \tau)$ 且 $q_\tau = \sum \min(\epsilon_i, \tau)^2$。

2. 唯一阈值 $\epsilon$ 估计量（简化基线）：

   • 该估计量选择一个单一的全局阈值 $\epsilon$。
   • 它丢弃所有个体需求 $\epsilon_i < \epsilon$ 的数据点。
   • 它对剩余的 $n_\epsilon$ 个数据点应用统一的隐私预算 $\epsilon$。
   • MSE 在 $\epsilon$ 的选择上最小化：
     $$\text{MSE}_{\text{thr}}(\epsilon) = \inf_{\epsilon>0} \left( \frac{1}{4n_\epsilon} + \frac{2}{\epsilon^2 n_\epsilon^2} \right)$$

指标

性能通过分布鲁棒均方误差（具有有界支撑集的分布上的最坏情况 MSE）来衡量。作者分析近似比 $\frac{\text{MSE}_{\text{thr}}}{\text{MSE}_{\text{aff}}}$，以量化使用简单阈值方法而非最优仿射机制时的效用损失。

主要贡献与结果

本文在三个不同的情形下，提供了阈值估计量与最优仿射估计量之间性能差距的精确界限：

1. 公共数据与私有数据的组合

• 设定： $n_1$ 个私有数据点（预算 $\epsilon_1$）和 $n_2$ 个公共数据点（有效 $\epsilon_2 = \infty$）的混合。
• 结果： 阈值估计量实现了最优仿射估计量的2 倍近似。
• 洞察： 差距是紧的，且仅在私有部分和公共部分的方差贡献平衡的狭窄区域趋近于 2。在其他大多数配置中，比率接近 1，表明个性化带来的收益微乎其微。

2. 两个有限隐私水平

• 设定： 数据点具有两个有限隐私预算之一，$\epsilon_1 < \epsilon_2$。
• 结果： 近似比从 2 下降到4。
• 洞察： 作者提供了一个反例，表明比率可以超过 2。然而，他们证明了无论 $\epsilon_1, \epsilon_2$ 的具体数值或数据计数如何，比率均被 4 所限制。这意味着即使在这个稍复杂的情形中，阈值方法也捕捉到了绝大部分效用。

3. 任意数量的隐私水平（$m$ 个水平）

• 设定： 数据点具有 $m$ 个不同的隐私水平（$0 < \epsilon_1 < \dots < \epsilon_m$）。
• 结果： 一般情况下不可能实现常数因子近似。
  • 下界： 作者构建了一个特定实例，其中比率随水平数量呈二次方增长：$\Omega(m^2)$。具体而言，如果 $m \approx \log_2 n$，则比率为 $\Omega((\log_2 n)^2)$。
  • 上界： 他们证明了对于任何实例，比率被 $\min((1 + \log_2 n)^2, m^2)$ 所限制。
• 洞察： 虽然差距理论上可能随隐私水平的数量增长，但这种增长是有限的（关于 $m$ 的二次方或关于 $n$ 的对数方）。“最坏情况”场景需要特定且略显人为的隐私水平和数据计数分布。

意义与主张

本文认为，在异构 DP 中实现高用度的主导因素是选择正确的有效隐私预算，而不是实施完全个性化。

• 有限的收益： 在最常见和实际的情形中（组合公共/私有数据或处理两个隐私水平），完全个性化仿射估计量带来的收益仅限于常数因子（最多 4 倍）。
• 阈值法的实用性： 阈值估计量提供了显著的实用优势：它更易于审计，允许更清晰地传达隐私保证，并能更简单地适应用户群的变化。它还为那些对数据更慷慨的智能体提供了“免费”的隐私。
• 理论极限： 虽然本文确立了差距可能随隐私水平数量（$m$）增长，但作者指出，即使在一般情形下，对于 $m > 2$ 的情况，最优个性化估计量甚至尚未被知晓。因此，阈值方法仍然是均值估计中一种稳健且接近最优的启发式方法。

作者得出结论：对于均值估计，完全个性化的复杂性通常无法被边际效用增益所证明是合理的，这表明更简单的阈值策略足以满足大多数感兴趣的情形。他们推测，类似的结论可能适用于更广泛的学习任务，尽管这仍是未来研究的一个开放领域。