当行列式不够用时：私有稀有切换

# 当行列式不再足够：私密稀有切换  
**来源：** https://arxiv.org/html/2605.23131  

###### 摘要  
在这篇笔记中，我想分享一个小型研究时刻，其中 Codex 帮助我找到了将稀有切换适配到私密环境的正确方法。线性老虎机和强化学习中基于行列式的标准更新规则之所以工作得非常好，是因为设计矩阵单调增长。但一旦为了隐私而加入高斯噪声，这种单调性可能失效，通常的分析也就不再成立。关键原因在于，行列式增长控制的是体积，而遗憾分析需要控制最差方向。为了解决这个问题，Codex 提出了一种基于广义瑞利商的不同稀有切换规则，该规则恢复了对数级别的策略更新，并实现了期望的置信宽度对比（仅差一个常数因子）。我在此展示了我手动清理过的证明版本，以及我对这个例子的一些个人反思。  

## 1 问题  
该问题是线性老虎机与强化学习中标准稀有切换策略更新的一种变体。让我们先回顾一下标准设置，即文献 [APS11](https://arxiv.org/html/2605.23131#bib.bibx1) 中的第 5.1 节。学习器维护一个正定协方差矩阵 \(V_t = \lambda I + \sum_{s=1}^t x_s x_s^\top\)，其中 \(t \in [T], \lambda > 0\)，并且仅当 \(\det(V_t) > \alpha \det(V_\tau)\)（其中 \(\alpha > 1\)，\(\tau\) 是 \(t\) 之前最近的更新时刻）时才更新策略。这个简单的规则通常被称为 *稀有切换更新*，它可以：(i) 将总策略更新次数减少到 \(O(\log T)\)（直接来自标准椭圆势引理，即 [APS11](https://arxiv.org/html/2605.23131#bib.bibx1) 中的引理 11）；(ii) 在遗憾上仅增加一个常数因子（直接来自 [APS11](https://arxiv.org/html/2605.23131#bib.bibx1) 中的引理 12）。特别地，[APS11](https://arxiv.org/html/2605.23131#bib.bibx1) 中的引理 12 表明：如果 \(V_t \succeq V_\tau\)，则对于任意 \(x \in \mathbb{R}^d\)，有 \(\|x\|_{V_\tau^{-1}} \leq \sqrt{\alpha} \|x\|_{V_t^{-1}}\)。  

那么，如果协方差矩阵受到扰动（例如由于隐私保护）呢？例如，在私密线性上下文老虎机或线性强化学习中，通常会在非私密矩阵上添加高斯噪声矩阵，得到私密矩阵 \(\widetilde{V}_t = V_t + E_t\)，其中 \(E_t\) 是对称矩阵，元素来自高斯分布。一个自然的问题是：我们是否仍然可以将上述更新规则（应用于 \(\widetilde{V}_t\)）及其分析应用于同样性能，即对数级别的更新次数和相同量级的遗憾？答案是否定的。原因是，要应用引理 12，我们必须保证单调性，即 \(\widetilde{V}_t \succeq \widetilde{V}_\tau\)。由于私密噪声的存在，这不再成立。这个问题已由我先前的工作 [CZ22](https://arxiv.org/html/2605.23131#bib.bibx2)（参见第 6 节）和最近的工作 [HZ26](https://arxiv.org/html/2605.23131#bib.bibx3)（参见附录 C）指出。我先前的工作 [ZR24](https://arxiv.org/html/2605.23131#bib.bibx4)（参见附录 C.3）也在不同的背景下发现了类似问题。  

因此，我们可能会问：*对于私密情况，是否存在新的稀有切换规则？* ¹  

## 2 新规则  
我基本上把上述内容写成提示，交给 Codex 5.5（极高模式），并附带了文件夹中的所有相关论文。Codex 的第一次尝试就给出了正确答案，总结在下面的定理中 ²。  

###### 定理 2.1。  
设 \(x_1, \ldots, x_T \in \mathbb{R}^d\) 满足对所有 \(t \in [T]\) 有 \(\|x_t\|_2 \leq L\)。令非私密设计矩阵为  
\[
V_1 := \lambda I, \quad V_{t+1} := V_t + x_t x_t^\top.
\]  
假设私密矩阵为 \(\widetilde{V}_t = V_t + E_t\)，其中 \(E_t\) 是对称矩阵，且对所有 \(t \in [T]\) 满足 ³  
\[
\|E_t\|_2 \leq \eta \quad \text{并且} \quad 0 \leq 2\eta \leq \lambda.
\]  
设有如下更新规则：对于任意 \(t \in [T]\)，当  
\[
\lambda_{\max}\left( \widetilde{V}_{\tau_t}^{-1/2} \widetilde{V}_t \widetilde{V}_{\tau_t}^{-1/2} \right) > \alpha
\]  
时更新策略，其中 \(\tau_t\) 是 \(t\) 之前最近的更新时刻。那么，令 \(\rho := \eta/\lambda\)，\(c_\rho := \frac{1+\rho}{1-\rho}\)，则有：  
1. **(i)** 对任意 \(x \in \mathbb{R}^d\) 和 \(t \in [T]\)，有  
   \[
   \|x\|_{\widetilde{V}_{\tau_t}^{-1}} \leq \sqrt{\alpha} \|x\|_{\widetilde{V}_t^{-1}} \quad \text{和} \quad \|x\|_{V_{\tau_t}^{-1}} \leq \sqrt{c_\rho \alpha} \|x\|_{V_t^{-1}};
   \]  
2. **(ii)** 总更新次数 \(m\) 的上界为  
   \[
   m \lesssim d \log_{\alpha/c_\rho}\left( 1 + \frac{TL^2}{\lambda d} \right) = O_d(\log T).
   \]  

###### 证明。  
我们首先给出以下声明，该声明对证明非常有用，其证明将在末尾给出。  

###### 声明 2.3。  
对于 \(1 \leq a \leq b \leq T\)，令  
\[
g_{a,b} := \lambda_{\max}\left( V_a^{-1/2} V_b V_a^{-1/2} \right) \quad \text{和} \quad \widetilde{g}_{a,b} := \lambda_{\max}\left( \widetilde{V}_a^{-1/2} \widetilde{V}_b \widetilde{V}_a^{-1/2} \right).
\]  
则有  
\[
c_\rho^{-1} g_{a,b} \leq \widetilde{g}_{a,b} \leq c_\rho g_{a,b}.
\]  

我们从 **(i)** 开始证明。对任意 \(\tau_t < t\)，由更新规则可知  
\[
g_{\tau_t, t} \geq c_\rho^{-1} \widetilde{g}_{\tau_t, t} > \alpha / c_\rho.
\]  
进一步，由于 \(V_t \succeq V_{\tau_t}\)，\(V_{\tau_t}^{-1/2} V_t V_{\tau_t}^{-1/2}\) 的所有特征值都至少为 1。因此，由上述结果和行列式的可乘性，有  
\[
\frac{\det(V_t)}{\det(V_{\tau_t})} = \det\left( V_{\tau_t}^{-1/2} V_t V_{\tau_t}^{-1/2} \right) > \alpha / c_\rho.
\]  
于是，根据椭圆势引理（见 [APS11] 中引理 11），总更新次数 \(m\) 的上界为  
\[
m \lesssim d \log_{\alpha/c_\rho}\left( 1 + \frac{TL^2}{\lambda d} \right).
\]  

剩下的是声明 2.3 的证明。首先注意，根据 \(E_t\) 的条件，有 \(-\eta I \preceq E_t \preceq \eta I\)。进一步，由于 \(V_t \succeq \lambda I\)，可得 \(\eta I \preceq (\eta/\lambda) V_t = \rho V_t\)。结合以上，有  
\[
(1-\rho) V_t \preceq \widetilde{V}_t \preceq (1+\rho) V_t.
\]  
因此，对任意非零向量 \(x \in \mathbb{R}^d\)，有  
\[
\frac{x^\top \widetilde{V}_b x}{x^\top \widetilde{V}_a x} \leq \frac{(1+\rho) x^\top V_b x}{(1-\rho) x^\top V_a x} = c_\rho \frac{x^\top V_b x}{x^\top V_a x}.
\]  
取上确界并应用广义瑞利商的恒等式，可得 \(\widetilde{g}_{a,b} \leq c_\rho g_{a,b}\)。另一方向同理可证。∎  

## 3 联系  
人们可能会好奇新更新规则与标准规则之间的区别或联系。为了说明这一点，考察新更新规则即使在非私密情况下的行为是有启发性的，然后判断它是否会导致更频繁或更稀疏的更新。为此，我直接将 [APS11](https://arxiv.org/html/2605.23131#bib.bibx1) 中引理 12 的截图输入给 Codex（以及 ChatGPT）。它随即给出了一个新的证明，实际上揭示了 Codex 是如何想到这个新更新规则及其与旧规则的关联的。这个新证明（至少对我来说）比原始证明简单得多。基本上，证明首先注意到引理 12 中的左边等于  
\[
\sup_{x \neq 0} \frac{x^\top A x}{x^\top B x} = \lambda_{\max}(B^{-1/2} A B^{-1/2}), \tag{1}
\]  
这里再次应用了广义瑞利商的恒等式，而引理 12 的右边等于  
\[
\frac{\det(A)}{\det(B)} = \det(B^{-1/2} A B^{-1/2}). \tag{2}
\]  
注意，由于单调性 \(B \preceq A\) 保证了 \(B^{-1/2} A B^{-1/2}\) 的所有特征值至少为 1，因此 (1) ≤ (2)。这就证明了引理 12。  

所以，本质上，新更新规则来源于引理 12 的新证明，即 (1)。此外，我们可以看到，在新更新规则下，学习器更新会更稀疏，因为 (1) > α 意味着 (2) > α，但反过来不成立。这个新证明也解释了为什么新更新规则能够摆脱旧规则在缺乏单调性时的问题。这是因为使用旧更新规则（即 (2)）时，必须进一步利用单调性来得到 \(\sup_{x \neq 0} \frac{x^\top A x}{x^\top B x}\)（即最差方向）的上界。而新规则直接作用于 \(\sup_{x \neq 0} \frac{x^\top A x}{x^\top B x}\)。我们现在也可以看到，使用旧更新规则，如果没有单调性，就无法控制最差方向，因为其他方向上的特征值可能小得多，最差方向上很大的值仍可使得行列式很小。  

## 4 反思  
Codex 为私密情况提出了一种新的稀有切换规则，保留了期望的保证。仔细审视后，该规则可以追溯到关键引理的另一个证明。证明中的各个要素并非新颖，但它们的选取、组合以及应用于正确的对象的方式才是关键。从这个意义上说，这个小例子与单位距离问题有几分相似的精神。  

这让我想起几件事。首先，对我来说，做研究最愉快的部分不一定在于其影响力，也不是最终的突破性成果。而在于我理解某件事更深一点的那个时刻 ⁴。从这个意义上说，研究本身携带着内在的回报。高中和大学时我至今还记得的一件事是，我经常去找老师或教授请教澄清问题，或者向他们解释我自己的理解，希望他们能确认 ⁵。现在，有了人工智能，学生们可能拥有更便捷的方式来测试、完善和验证他们自己的理解（如果他们愿意的话……）。  

其次，我倾向于将深入理解一个主题视为学习一个好的表示。一个好的表示将许多细节压缩成正确的概念，因此它在适应新问题时具有灵活性和实用性。在许多情况下，要产生显著影响（无论是理论上还是实践上），并不一定需要全新的理论或方法。相反，它可能来源于对现有知识的更好压缩或表示，这种表示能够识别出“核心集”，从而可以探索一个更大的未知空间。  

因此，借助今天的人工智能工具，人类可能更有效地最大化这种内在回报：理解得更深、澄清得更快、构建更好的表示。也许我们还应该思考如何在训练或测试时扩展中引导人工智能系统朝类似的目标发展：不仅仅是产生答案，而是主动寻找好的表示、有用的抽象和核心思想。对我而言，这自然联系到强化学习中“探索”这一基本问题，这也是我目前最大的兴趣所在。  

## 参考文献  
- [APS11] Yasin Abbasi-Yadkori, Dávid Pál 和 Csaba Szepesvári.“Improved algorithms for linear stochastic bandits”. 在 *Advances in neural information processing systems* 24, 2011.  
- [CZ22] Sayak Ray Chowdhury 和 Xingyu Zhou.“Shuffle Private Linear Contextual Bandits”. 在 *International Conference on Machine Learning*, 2022, pp. 3984–4009. PMLR.  
- [HZ26] Yi He 和 Xingyu Zhou.“Towards Differentially Private Reinforcement Learning with General Function Approximation”. 在 *arXiv preprint arXiv:2605.07049*, 2026.  
- [ZR24] Xingyu Zhou 和 Sayak Ray Chowdhury.“On differentially private federated linear contextual bandits”. 在 *International Conference on Learning Representations* 2024, 2024, pp. 30101–30131.  

---

¹ 当然，有人可能会问：是否可以保持相同的更新规则，但使用更先进的分析来维持相同的性能保证？事实证明这是不可能的，这将在本文末尾变得清楚。  

² 我对 Codex 的原始证明进行了清理和重新组织，原始证明是正确的但不易阅读。  

³ 对于高斯矩阵，该条件以高概率成立。  

⁴ 当然，这是一种特权。而且，也可能导致一种尴尬的结果：既没有影响力，也没有深入理解。你可以在这里点名我。  

⁵ 用今天时髦的话说，我在尝试构建和校准自己的世界模型。