技术摘要：面向无限流估计的个性化 w-事件隐私保护

1. 问题定义

本文解决了在保护个人用户隐私（基于差分隐私 DP）的前提下，对无限数据流进行统计量估计的挑战。现有的 w-事件隐私（保护用户在连续 $w$ 个时间槽内的滑动窗口内的数据）方法通常执行同质化要求，即对所有用户应用统一的隐私预算 ($\epsilon$) 和窗口大小 ($w$)。

这种“一刀切”的方法在现实场景中并非最优，因为用户具有不同的隐私偏好。例如，一位名人可能需要对位置数据进行强保护（大 $w$，小 $\epsilon$），而一位街头艺术家可能更倾向于较弱的保护以最大化曝光度。为所有用户强制执行最严格的要求会导致过高的统计误差（低效用），而执行最宽松的要求则无法保护敏感用户。

本文形式化了两种问题设置：

1. 固定个性化设置 (PWEPP-IDS)： 每个用户 $u_i$ 拥有由固定的窗口大小 $w_i$ 和固定隐私预算 $E_i$ 定义的静态隐私需求。
2. 动态个性化设置 (DPWEPP-IDS)： 用户可以指定随时间变化的隐私需求。在每个时间槽 $t$，用户声明一个向后需求（窗口 $w_{B,i,t}$，预算 $E_{B,i,t}$）覆盖近期过去，以及一个向前需求（窗口 $w_{F,i,t}$，预算 $E_{F,i,t}$）覆盖即将到来的未来。

核心挑战在于在线可行性 (Online Feasibility)：系统必须在每个时间槽发布一个单一的共享聚合统计量，该统计量必须同时满足所有用户的异构、时变约束，并确保与已消耗的预算保持一致，且对未来的需求具有可行性。

2. 方法论

作者提出了一个统一的框架，将异构的用户需求转化为有效的系统级发布决策。该框架由两个主要部分组成：用于固定设置的个性化窗口大小机制 (PWSM) 和用于动态设置的动态个性化窗口大小机制 (DPWSM)。

2.1 核心组件

• 最优预算选择 (OBS)： 给定一组异构隐私预算，OBS 选择一个最优阈值 $\epsilon_{opt}$，以最小化总报告误差。误差由采样误差（来自预算低于阈值的用户）和噪声误差（来自应用于该阈值的拉普拉斯机制）组成。
• 个性化隐私差异度量： 为了决定是发布一个新的模糊化统计量还是重用上一个统计量（从而节省预算），系统会计算当前数据与上次发布数据之间的差异性。该计算使用一部分隐私预算进行隐私化处理。
• 自适应发布策略： 如果私有差异度超过了预期噪声误差的平方根，则发布新的统计量；否则，系统跳过发布（空发布），用上一个值近似当前值。

2.2 固定设置解决方案 (PWSM)

对于固定设置，该框架通过两种机制进行实例化：

1. 个性化预算分配 (PBD)：
   • 将每个用户的总预算 $E_i$ 分为两半：一半用于差异度计算，一半用于发布。
   • 发布预算在窗口内均匀分布（$E_i / 2w_i$）。
   • 如果发生了发布，则调整当前窗口的剩余预算。如果差异度较低，则为未来的时间槽节省预算。
2. 个性化预算吸收 (PBA)：
   • 旨在实现更平滑的流处理。它允许在时间 $t$ 的发布“借用”用户窗口内未来时间槽的预算份额。
   • 如果某次发布使用的预算超过了平均份额，则后续的时间槽将被“置空”（跳过），以维持平均预算约束。
   • 该机制通过跳过未来低效用的发布，来吸收高效用发布的成本。

2.3 动态设置解决方案 (DPWSM)

对于动态设置，该框架推广为 DPBD 和 DPBA。这些机制引入了可行性条件来处理随时间变化的约束：

• 向后可行性 (Backward Feasibility)： 时间 $t$ 使用的预算不得超过当前向后窗口的剩余预算（$E_{B,i,t}$ 减去历史消耗）。
• 向前可行性 (Forward Feasibility)： 时间 $t$ 使用的预算不得违反任何先前声明的、其向前窗口覆盖了 $t$ 的时间槽 $\tau$ 的向前隐私要求。
• 机制逻辑：
  • DPBD： 通过取当前向后剩余预算与所有活跃向前窗口导出的向前剩余预算的最小值，计算每个用户的可行预算上限。然后将此可行预算分为差异度和发布两部分。
  • DPBA： 将吸收逻辑扩展到动态窗口。它根据历史向前需求为每个用户计算一个“向前置空右边界”。如果当前时间槽处于该边界内，则跳过发布。否则，它会在尊重所有活跃向前约束的前提下，计算可吸收的最大未来预算。

3. 主要贡献

1. 问题形式化： 本文定义了面向无限数据流的动态个性化 w-事件隐私发布 (DPWEPP-IDS)，将固定个性化设置推广到允许随时间变化的向后和向前隐私需求。它引入了隐私概念 $(\tau, w_B, w_F, E_B, E_F)\text{-EPDP}$。
2. 在线可行性挑战： 它识别并解决了在异构、时变的约束下，维护一个单一共享发布必须满足所有用户重叠窗口的全新挑战。
3. 统一框架： 作者提出了一个统一框架 (PWSM/DPWSM)，利用 最优预算选择 (OBS) 和自适应发布策略，将异构的个性化需求转换为共享的发布决策。
4. 机制：
   • PBD & PBA： 用于固定个性化设置的解决方案。
   • DPBD & DPBA： 严格执行向后和向前可行性的动态个性化设置解决方案。
5. 理论保证： 论文证明了所有机制都满足相应的个性化差分隐私定义，并建立了平均误差（效用）的理论上界。
6. 实验验证： 在真实和合成数据集上的广泛实验表明，所提出的机制在效用方面显著优于经典的同质化基准（BD 和 BA）。

4. 实验结果

作者在真实和合成数据集上评估了这些机制。

• 性能： 所提出的方法在效用上始终优于经典的同质化基准。
  • 对于真实数据集，DPBD 与标准的预算分配 (BD) 方法相比，将平均相对误差 (AMRE) 降低了至少 62.7%。
  • 对于合成数据集，DPBA 与标准预算吸收 (BA) 方法相比，将 AMRE 降低了至少 53.6%。
• 可扩展性： 理论分析表明，其时间复杂度与用户数量 ($n$) 及最大窗口大小呈线性关系，使得该方法在大规模用户群体中具有可扩展性。

5. 重要性与主张

本文声称其主要贡献不仅在于用个性化参数取代全局参数，而是在于在重叠、异构且随时间变化的约束下，构建并维护一个有效的共享发布预算。

• 泛化性： 这项工作将 w-事件隐私范式扩展到了一个更通用、更实用的场景，即隐私偏好随时间演变的场景。
• 可行性： 它解决了确保单一聚合发布既与历史预算消耗一致，又与未来隐私可行性保持一致的非平凡问题，而这在经典的同质化 w-事件隐私中是不存在的。
• 实用性： 通过允许用户设置不同的隐私水平，系统避免了在“过度保护”某些用户（导致高误差）与“保护不足”其他用户之间进行权衡。结果表明，个性化机制可以在不损害个体所需特定隐私保证的前提下，实现显著更高的数据效用。

作者强调，虽然受信任的查询者假设是中心化流发布的标准做法，但所提出的机制专门解决了处理异构和动态隐私需求的空白，而现有的中心化方法（如 BD, BA, RescueDP, SPAS）并不支持这一点。