](https://deep-paper.org/en/paper/2506.05503/images/cover.png)
在算法设计的世界里，数据结构与“对手” (即生成输入的实体) 之间存在着持续的军备竞赛。传统的随机算法在对抗遗忘型对手 (oblivious adversary) 时表现出色，这种对手会预先生成一系列查询，且不知道算法内部的随机硬币翻转结果。
但是，当对手是自适应 (adaptive) 的，情况会怎样？想象这样一种场景: 一个用户 (或攻击者) 查询你的数据库，看到结果后，利用该信息来构建一个特别棘手的下一个查询。这就产生了一个反馈循环。输出结果泄露了关于算法内部随机性的信息，使得对手能够将其输入与你的私有随机种子“关联”起来，最终打破系统的正确性保证。
对于高维搜索和优化来说，这是一个巨大的问题。为了处理 \(T\) 个自适应查询，朴素的解决方案是运行 \(T\) 个独立的数据结构副本，并为每个查询切换到一个全新的副本。这会彻底破坏效率。
在论文 “On Differential Privacy for Adaptively Solving Search Problems via Sketching” (利用差分隐私通过草图技术自适应求解搜索问题) 中，研究人员提出了一种复杂的框架，利用差分隐私 (Differential Privacy, DP) 不是为了保护用户数据，而是为了保护算法的内部随机性。通过使算法的输出相对于其自身的随机种子“私有化”，他们阻止了对手学习到足够的信息来破坏系统。
本文将拆解他们如何针对两大主要问题实现这一目标: 近似最近邻 (ANN) 搜索和自适应线性回归 。
核心概念: 隐私即稳健性
这项研究的核心洞见建立在一个日益增长的趋势之上: 将差分隐私 (DP) 作为算法稳定性的工具。
在经典定义中，如果当我们改变输入数据库中的单个元素时，算法 \(\mathcal{A}\) 的输出分布没有发生太大变化，那么该算法就是 \((\varepsilon, \delta)\)-差分隐私的。
在此背景下，“数据库”并非用户记录，而是这组数据结构所使用的随机字符串集合 。 如果我们的搜索问题的输出相对于这些随机字符串是差分隐私的，那么输出就不会泄露关于任何特定随机字符串的太多信息。因此，自适应对手无法轻易利用随机化中的特定弱点。
先前的研究证明，对于数值型问题 (如估计回归成本) ，你只需要 \(\tilde{O}(\sqrt{T})\) 个数据结构副本，而不是 \(T\) 个。但这篇论文提出了更难的问题: 对于输出是高维向量的搜索问题，我们能做到这一点吗?
第一部分: 自适应近似最近邻 (ANN)
第一个挑战是近似最近邻问题。给定数据集 \(U\) 和查询 \(v\)，我们要找到 \(U\) 中接近 \(v\) 的一个点。
设置
我们要支持 \(T\) 个自适应查询。我们维护 \(k \approx \sqrt{T}\) 个遗忘型 ANN 数据结构 (如局部敏感哈希 - LSH) 的副本。 对于特定的查询 \(v_t\)，我们不仅仅查询一个 LSH，而是对它们进行小批量采样。
问题: 信息泄露
如果我们简单地输出一个 LSH 的结果，我们就准确地泄露了该查询在该特定随机种子下落入了哪个“桶”。对手可以利用这一点来测绘哈希函数的几何结构。
解决方案: 差分隐私选择
研究人员将采样到的 LSH 结构输出视为“投票”。如果多个数据结构返回同一个点 \(u \in U\) 作为邻居，该点就会获得更多选票。
为了保护随机种子的隐私，我们不能直接选择获胜者。我们必须使用一种带噪声的投票机制 。 具体来说，他们采用了指数机制 (Exponential Mechanism) 的一种变体:
- 统计每个候选点被多少个数据结构返回。
- 给这些计数添加随机噪声。
- 返回具有最大噪声计数的候选点。
所使用的噪声分布是指数分布 :
“稀疏 Argmax” 技巧
这里存在一个计算障碍。点集 \(U\) 的全集可能非常巨大 (\(n\) 个点) 。我们要想对每个查询都为数据库中的每个点生成噪声投票计数，需要 \(O(n)\) 的时间，这将违背亚线性搜索的初衷。
作者引入了 稀疏 Argmax 机制 (Sparse Argmax Mechanism) 。 他们观察到，对于任何查询，LSH 结构实际返回的点数 (\(s\)) 很少。“投票”向量极其稀疏；大多数点只有零票。
该算法仅为稀疏的非零条目生成噪声。对于数百万个零票点，他们利用顺序统计量逻辑 (计算空桶的“最大噪声”) 在 \(O(1)\) 时间内有效地采样 \(n\) 个独立噪声变量的最大值。这保持了查询时间的高效性:
这里，\(s\) 代表邻域的稀疏度——大致是我们预期找到多少个候选邻居。只要邻域不是太稠密 (这一属性在假设 1.3 中被形式化) ，该方法就能提供自适应安全性，且空间复杂度相比朴素方法有巨大提升。
第二部分: 自适应线性回归
第二个主要贡献涉及求解线性回归 \(\min_x \|U_t x - b_t\|_2\)，其中矩阵 \(U\) 和向量 \(b\) 不断被对手更新。
草图 (Sketching) 方法
处理巨型矩阵的标准做法是草图技术 。 我们将输入乘以一个随机矩阵 \(S\) (如 CountSketch 或下采样随机哈达玛变换 - SRHT) ，将矩阵的高度从 \(n\) 压缩到 \(r\)，其中 \(r \ll n\)。然后我们求解这个小规模的回归问题。
聚合挑战
为了处理自适应性，我们再次维护 \(k \approx \sqrt{T}\) 个草图。当查询到来时，我们采样几个草图并求解它们，得到一组候选解向量 \(x_{(1)}, \dots, x_{(s)}\)。
我们如何私有地组合这些向量？我们不能简单地取平均值 (对离群值敏感) 。提出的解决方案是逐坐标差分隐私中位数 (Coordinate-wise Private Median) 。
对于每个坐标 \(j \in [d]\):
- 收集所有候选向量的第 \(j\) 个坐标。
- 计算这些标量值的差分隐私中位数。
- 组装结果向量 \(g\)。
\(\ell_\infty\) 保证
这正是数学上棘手的地方。标准的草图技术保证保留回归的成本 (残差的 \(\ell_2\) 范数) 。它通常不保证解向量 \(x\) 在每个坐标上都接近最优解 \(x^*\)。
然而，如果误差集中在一个坐标上，逐坐标中位数可能会失败。作者证明，对于特定的草图 (如 SRHT 与 CountSketch 组合) ，草图解满足更强的 \(\ell_\infty\) 保证 :
这个界限确保了误差分散在各个坐标上。这使得逐坐标中位数能够重构出一个在预测成本方面接近最优解 \(x^*\) 的解向量。
通过结合矩阵的最大和最小奇异值，他们推导出了最终的效用界限:
这种方法允许极其高效的数据结构。如下表所示，空间复杂度随 \(\sqrt{T}\) 缩放，而不是 \(T\) 或 \(n\)，当 \(T\) 很大时提供了巨大的改进。
第三部分: 处理病态矩阵
上述回归策略依赖于条件数 \(\kappa\) (最大奇异值与最小奇异值之比) 在合理范围内。如果 \(\kappa\) 巨大，\(\ell_\infty\) 保证会变得太松，误差会爆炸。
对于这些“困难”情况，作者转向了另一种技术: 有界计算路径 (Bounded Computation Paths) 。
洞见
即使对手是自适应的，算法与对手之间的交互也可以被视为决策树上的一条路径。如果我们将算法的输出舍入到离散网格 (有限精度) ，算法可能生成的总输出序列 (路径) 数量是有限的，记为 \(|\mathcal{P}|\)。
我们不需要针对无限的可能性保持稳健，只需要针对 \(\mathcal{P}\) 中所有可能的计算路径的联合界 (union bound) 幸存下来即可。
算法
- 使用单个非常大的草图 (比通常更大，与 \(\log |\mathcal{P}|\) 成对数关系) 。
- 求解回归。
- 将解舍入到预定义网格上的最近点。
这种舍入有效地限制了对手基于输出的微小变化来微调输入的能力。代价是依赖于 \(\log |\mathcal{P}|\)，但对条件数 \(\kappa\) 的依赖从多项式级降低到了对数级。
通过批处理实现更快的更新
最后，论文解决了更新的实际成本问题。在如在线加权匹配等高频场景中，为每个输入更新 \(\sqrt{T}\) 个数据结构太慢了。
作者利用快速矩形矩阵乘法 (Fast Rectangular Matrix Multiplication) 。 他们不急于立即更新，而是缓冲更新并分块处理。通过仔细调整块大小 \(\theta\)，他们摊销了应用 Johnson-Lindenstrauss 变换的成本。
这种批处理使得“隐私即稳健性”框架不仅在理论查询复杂度上具有竞争力，而且在实际更新时间上也具有竞争力。
结论
这项研究弥合了两个截然不同领域之间的鸿沟: 差分隐私和流算法。它证明了隐私工具不仅仅用于保护敏感数据；它们还是稳定算法以对抗最坏情况自适应输入的强大数学工具。
通过结合用于搜索的 稀疏 Argmax 选择 和用于回归的 逐坐标中位数 , 作者提供了一个通用的配方，可以将遗忘型静态数据结构转换为稳健的自适应动态数据结构，且仅需承担平方根级别的开销惩罚。
注: 本文显示的图片直接提取自源论文 “On Differential Privacy for Adaptively Solving Search Problems via Sketching”，用于说明核心数学概念。