📊 statistics

AdaPrivate-TS: Private Thompson Sampling for Contextual Bandits with Privacy Amplification

AdaPrivate-TS 是一种差分隐私上下文多臂老虎机算法，它通过将隐私噪声解释为汤普森采样（Thompson Sampling）中增加的不确定性来发挥作用，并通过使用批处理 zCDP 组合与隐私放大技术，实现了具有对数级隐私成本的近乎最优的性能。

原作者： Mohammadreza Riyazat, Eranga Ukwatta

发布于 2026-06-23

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Mohammadreza Riyazat, Eranga Ukwatta

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你是一位正试图为一道新菜谱创造完美配方的厨师。你有一份食材清单（即“上下文”），你需要决定组合哪些食材进行烹饪（即“动作”），以获得最好的味道（即“奖励”）。问题在于，你还不知道确切的食谱，所以你必须不断实验。这就是**上下文多臂老虎机（Contextual Bandits）**的世界——一个高级术语，用于描述在线推荐系统（比如 Netflix 向你推荐电影或 Spotify 向你推荐歌曲）。

然而，这里有一个陷阱：为了学习人们喜欢什么，你需要看到他们的私密数据（他们点击了什么、评分了什么或购买了什么）。用户不希望自己的秘密被泄露。这就是**差分隐私（Differential Privacy, DP）**发挥作用的地方——它就像是在数据中添加了一层“雾”或“静电”，使得没有人能确切知道某个特定的人做了什么，但同时仍能让厨师学习到普遍的趋势。

现有方法的问题在于，这种“雾”通常会破坏学习过程。这就像是戴着厚厚的手套去品尝汤的味道；你无法很好地感知风味，因此会做出错误的判断。

核心理念：化“雾”为“特征”

该论文的作者 Mohammadreza Riyazat 和 Eranga Ukwatta 提出了一种聪明的全新算法，名为 AdaPrivate-TS。他们的秘诀在于视角的转变。

大多数算法将隐私“雾”视为损坏——一种破坏数据的错误。它们试图对抗或忽略这种雾，但这会导致性能低下。

作者意识到，他们所使用的特定方法——汤普森采样（Thompson Sampling）——并不把雾视为错误。相反，它将雾视为不确定性。

类比：
想象你是一名正在侦破谜案的侦探。

旧方法 (UCB)： 你有一份嫌疑人名单。如果证据很模糊（存在隐私噪声），你会感到困惑并做出僵化、谨慎的猜测。你可能会错过真正的罪犯，因为你太害怕猜错。
新方法 (AdaPrivate-TS)： 你是一名热爱猜测的侦探。当证据模糊时，你会想：“啊，这是一个棘手的案件！我不确定谁是凶手，所以我应该探索更多的可能性。”这种“雾”实际上让你变得更加好奇，并更愿意尝试不同的嫌疑人。

用技术术语来说，隐私噪声放大了算法的“不确定性”。这并没有破坏系统，反而告诉算法：“嘿，变得更有冒险精神吧！”这把一个弱点（隐私噪声）转化为了一个优势（更好的探索）。

他们是如何做到的：“批处理”技巧

为了高效地实现这一点，他们使用了一种称为**批处理（Batching）**的技术。
他们没有在每一次用户交互后都添加隐私噪声（这会非常昂贵且缓慢），而是等待积累一小组交互（一个“批次”）后，再为整个小组统一添加一次噪声。

类比：
想象你正在给朋友写信。

旧方法： 你写一封信，把它装进一个特殊的隐私信封，然后立即寄出。接着你写另一封，装入信封，再寄出。这很慢，而且消耗了很多信封。
新方法： 你写了 30 封信，把它们全部装进一个大箱子里，然后对整个箱子添加一个隐私封条。你一次性寄出这个箱子。
这种“批处理”方法允许他们将隐私成本分摊到多次交互中，使系统运行得更快、更准确。

“子采样”的助力

他们还发现了一种可以在不损失准确性的情况下增强隐私强度的方法，称为隐私放大（Privacy Amplification）。
类比： 想象你正在进行民意调查。与其询问人群中的所有人，不如随机抽取一小部分人（例如 30% 的人群）。因为你只观察一个随机的切片，所以很难通过观察来确定任何特定个体说了什么。这使得他们可以使用较少的“雾”（噪声）来保持同样的隐私保护水平。

他们的发现

他们通过两种方式测试了这位新厨师（AdaPrivate-TS）与旧厨师（其他算法）的表现：

模拟数据 (Synthetic)： 他们创建了一个包含 10,000 次交互的计算机模拟。
真实数据： 他们使用了真实世界的数据集，如 MovieLens（电影评分）和 Jester（笑话评分）。

结果：

更好的性能： 即使在严格的隐私规则下，他们的算法也能达到无隐私系统性能的 93% 到 99%。
击败竞争对手： 它始终优于之前的最佳方法（如 UCB），领先幅度在 0.5% 到 3.7% 之间，而在隐私规则非常严格时，领先幅度甚至高达 18%。
稳定性： 当隐私噪声冲击系统时，旧算法会踉跄并导致性能下降。而新算法则保持稳步上升，证明了将噪声视为“不确定性”能让系统更加稳定。
隐私特征： 即使在特征（例如电影的描述）也受到隐私保护的情况下，他们的算法依然胜出，这表明这种“噪声即不确定性”的思想在许多不同场景下都是有效的。

总结

该论文声称，通过改变我们看待隐私噪声的方式——将其视为一种鼓励探索的特征，而非一个漏洞——我们可以构建既尊重用户隐私又能保证推荐质量的推荐系统。这就像是在雨中学会起舞，而不是试图阻止降雨。

技术摘要：AdaPrivate-TS

问题陈述

在线推荐系统面临着一个根本性的矛盾：一方面需要从私有的行为数据中学习用户偏好，另一方面需要提供严格的隐私保护。虽然差分隐私（Differential Privacy, DP）提供了强大的保护，但它通常会引入噪声，从而降低学习性能。现有的私有上下文多臂老虎机（Contextual Bandit）算法通常将隐私噪声视为纯粹的破坏，这导致了显著的遗憾值（Regret）。此外，许多方法依赖于联合 DP（保护整个动作序列）或顺序组合（Sequential Composition），这会导致高昂的隐私成本（例如 $O(T^{3/4})$ 的遗憾值），或者需要一个受信任的中央库（Central Curator）。

本文旨在解决设计一种能够在事件级 DP（保护单个用户-奖励对）下运行、针对随机上下文（Stochastic Contexts）的差分隐私上下文老虎机算法的挑战，目标是在保持严格隐私的同时最小化遗憾值，且无需受信任的中央实体。

方法论：AdaPrivate-TS

作者提出了 AdaPrivate-TS，这是一种将汤普森采样（Thompson Sampling, TS）与分批零浓度差分隐私（Batched zero-concentrated Differential Privacy, zCDP）相结合的新颖算法。

核心洞察：噪声即不确定性

其核心理论贡献在于观察到：当向线性老虎机的充分统计量（Sufficient Statistics）中添加 DP 噪声时，该噪声不仅仅是破坏了估计值，而且在结构上放大了后验协方差。

在标准的汤普森采样中，后验分布为 $\theta | H_t \sim \mathcal{N}(\hat{\theta}_t, v^2 A_t^{-1})$ 。
当为了隐私目的向充分统计量 $b_t$ 添加高斯噪声 $\eta \sim \mathcal{N}(0, \sigma^2 I)$ 时，得到的采样分布变为：
$\tilde{\theta}_t \sim \mathcal{N}\left(\hat{\theta}_t, v^2 A_t^{-1} + \sigma^2 A_t^{-2}\right)$
与将此噪声视为误差的置信上限（UCB）方法不同，汤普森采样能够自然地将这种放大的协方差（ $v^2 A_t^{-1} + \sigma^2 A_t^{-2}$ ）解释为增加的不确定性。这促使算法在隐私噪声占主导地位的方向上进行更多探索，有效地将“破坏”转化为有益的探索信号。

算法组件

分批 zCDP 组合： 该算法按批次处理交互。它在每个批次结束时发布带有噪声的充分统计量（特别是向量 $b$ ）。通过使用并行组合（Parallel Composition），总隐私成本由单个批次的最大成本（ $\max_k \rho_k = \rho$ ）决定，而不是成本之和，从而使隐私成本保持为 $T$ 的对数级。
隐私放大： 为了在严苛的隐私预算（ $\epsilon \leq 1$ ）下进一步减少噪声，作者采用了泊松子采样（Poisson Subsampling）。通过以概率 $q$ 包含每个批次中的奖励和，在不重新缩放敏感度的情况下，利用 Rényi 差分隐私（RDP）分析将有效隐私成本降低约 $2q^2$ 倍。
自适应探索： 算法随时间衰减探索参数 $v_k$ （即 $v_k = v_0 \cdot \gamma^{k-1}$ ），以平衡早期的激进探索与模型收敛后的精细利用。

隐私模型

该算法满足事件级 DP，其中相邻数据集仅在一个用户-奖励对 $(u_t, r_t)$ 上存在差异。动作被视为算法的输出，而非私有输入。该机制使用 zCDP 进行更紧密的组合分析，并通过标准转换公式转换为 $(\epsilon, \delta)$ -DP。

核心贡献

私有汤普森采样： 本文证明了向充分统计量添加 DP 噪声会导致特定的后验协方差放大（ $v^2 A^{-1} + \sigma^2 A^{-2}$ ）。这使得 TS 能够将噪声解释为不确定性而非破坏。
紧凑的遗憾值界限： 在具有随机上下文的事件级 DP 下，作者证明了其遗憾值界限为 $O(\sqrt{d} \cdot \log T / \sqrt{\rho})$ 。该结果相对于 $T$ 是对数级的，相比于顺序组合或联合 DP 带来的 $O(\sqrt{T})$ 或 $O(T^{3/4})$ 成本有了显著改进。
隐私放大分析： 提供了一个基于 RDP 的针对老虎机的泊松子采样的严谨分析，证明了在低 $\epsilon$ 值下可获得 2–4% 的收益。
全面的评估： 通过在合成数据集和真实世界数据集（MovieLens-25M, Jester）上的广泛实验验证了理论主张。

实验结果

对比非私有性能： 在隐私预算 $\epsilon \in [0.5, 5]$ 范围内，AdaPrivate-TS 达到了非私有汤普森采样性能的 93–99%。
对比 UCB： 该算法在平均水平上优于私有 UCB 基准 0.5–3.7%。通过调整自适应探索，在极端隐私设置下，其优势可扩大至 高达 18%。
真实世界数据： 在 MovieLens 和 Jester 数据集上，AdaPrivate-TS 在所有事件级基准中表现最佳，尤其是在 $\epsilon \geq 2$ 时占据主导地位。
特征隐私： 当使用 DP-SVD 对特征进行隐私化处理时，TS 相对于 UCB 的优势增加到了 +11%，这证实了“噪声即不确定性”机制不仅适用于奖励隐私，也适用于特征隐私。
消融实验： 组件分析表明，TS、隐私放大和自适应探索的结合，比带有噪声的基准私有 UCB 实现了 +6.3% 的累积增益。

意义与主张

本文声称，汤普森采样在本质上比 UCB 更适合私有上下文老虎机，因为它能够利用 DP 噪声的结构特性作为探索来源，而非将其视为误差来源。

关于其重要性的关键主张包括：

高效性： 使用并行组合配合分批处理，使得隐私成本与时间跨度 $T$ 成对数关系，避免了顺序组合带来的严重惩罚。
实用性： 该算法无需受信任的中央库即可运行，仅依赖事件级隐私，这适用于用户仅贡献少量交互的场景。
鲁棒性： 该方法在私有特征（DP-SVD）下依然保持稳定，并提供了一种通过泊松子采样在不牺牲推荐质量的前提下收紧隐私预算的原则性方法。
理论新颖性： 识别出噪声诱导的协方差放大作为“噪声即不确定性”机制的过程，为设计私有学习算法提供了新的视角，超越了仅将隐私噪声视为破坏的范式。

作者总结道，AdaPrivate-TS 为需要平衡严格隐私要求与高质量推荐性能（特别是在具有随机上下文和事件级隐私约束的场景下）的从业者提供了一个原则性的工具。