Private Continual Counting of Unbounded Streams¶

会议: NeurIPS 2025
arXiv: 2506.15018
代码: GitHub
领域: AI安全
关键词: 差分隐私, 持续观测, 矩阵分解, 流式计算, 无界输入

一句话总结¶

提出基于对数扰动的新型矩阵分解方法，首次实现同时满足"无界流"、"平滑误差"和"近最优渐近误差"三大性质的差分隐私持续计数算法，对任意 \(\alpha > 0\) 在时间步 \(t\) 处的方差为 \(O(\log^{2+2\alpha}(t))\)。

研究背景与动机¶

差分隐私持续计数是指在敏感数据流上维持准确的运行总和。这一问题在隐私优化（如联邦学习、私有梯度下降）、在线学习和流式数据分析中有广泛应用，Google 的私有 next-word prediction 和 Smart Select 模型等大规模隐私部署都依赖于此。

近年来，基于矩阵分解的算法（特别是 \(M_{\text{count}}^{1/2}\) 分解）大幅改善了经典二叉树方法的隐私-效用权衡。然而，这些 SOTA 算法有一个根本假设：需要提前知道输入大小 \(n\)。这一假设在模型训练等场景中自然成立，但在公共卫生监测等应用中不现实。

Apple 在部署差分隐私收集用户数据时，因为这一问题而只能保证单日隐私，导致用户隐私损失随时间无限增长——这一著名案例说明了无界输入问题的实际影响。

现有解决方案都面临根本性权衡（三难困境）： - 倍增技巧：保持渐近性能但导致非平滑的误差增长 - 固定预算：保持性能和平滑性但不是真正无界——隐私预算耗尽后停止 - 独立噪声：天然无界且平滑，但误差极其次优

方法详解¶

整体框架¶

核心思路是寻找特殊的解析函数来构造下三角 Toeplitz（LTToep）矩阵分解 \(L \cdot R = M_{\text{count}}\)，使得 \(R\) 的列范数有界（从而可无界使用），同时 \(L\) 的行范数增长尽可能慢（接近最优误差）。关键创新是在 \((1-z)^{-1/2}\)（即 \(M_{\text{count}}^{1/2}\) 对应的函数）上引入对数扰动，使其变为 \(L^2\) 可积，从而实现无界输入。

关键设计¶

对数扰动矩阵分解：
- 定义生成函数族：\(f(z;\gamma,\delta) = f_1(z) \cdot f_2(z;\gamma) \cdot f_3(z;\delta)\)
- 其中 \(f_1(z) = \frac{1}{\sqrt{1-z}}\)，\(f_2(z;\gamma) = (\frac{1}{z}\ln\frac{1}{1-z})^\gamma\)，\(f_3(z;\delta) = (\frac{2}{z}\ln\frac{1}{z}\ln\frac{1}{1-z})^\delta\)
- 取 \(R = \text{LTToep}(f(z; -\frac{1}{2}-\alpha, \delta))\)，\(L = \text{LTToep}(f(z; \frac{1}{2}+\alpha, -\delta))\)
- 设计动机：直接对 \((1-z)^{-1/2}\) 做幂次调整（如 \((1-z)^{-1/2+\alpha}\)）会导致 \(O(t^\alpha)\) 误差，因为 \((1-z)^{-\alpha}\) 在 \(z \to 1^-\) 时发散太快。而 \(\ln(1/(1-z))\) 发散更慢，能将误差控制在对数级别
四大性质证明（定理 1）：
- 联合有效性：\(LR = \text{LTToep}(f_L \cdot f_R) = \text{LTToep}(\frac{1}{1-z}) = M_{\text{count}}\)
- 有界灵敏度：利用 Flajolet-Odlyzko 渐近展开证明 \([z^n]f_R\) 的平方和收敛（当 \(\gamma < -1/2\) 时），并通过 Parseval 定理精确计算 \(\|R\|_{1 \to 2}^2 = \frac{1}{2\pi}\int_0^{2\pi}|f_R(e^{i\theta})|^2 d\theta\)
- 近最优渐近误差：\(\|[L]_n\|_{2 \to \infty} = O(\log^{1+\alpha}(n))\)
- 可计算性：通过 FFT 实现 \(O(t)\) 空间、分摊 \(O(\log t)\) 每步时间
参数选择策略：
- \(\alpha\) 选择：设 \(\alpha = 0.01\) 对全球人口（8.2B 人×100 数据点）仅引入 1.03 倍开销
- \(\delta\) 选择三种方案：\(\delta = 0\)（最快）、\(\delta = -\gamma\)（更优误差，约 1.5 倍慢）、\(\delta = -6\gamma/5\)（使前两个 Taylor 系数精确匹配 \(M_{\text{count}}^{1/2}\)，\(t > 2^{20}\) 时最优）
- 设计动机：参数空间虽大但理论分析和实验都指向少数几个最优选择

损失函数 / 训练策略¶

本文为理论工作，核心算法（Algorithm 1）： - 初始化时通过数值积分精确计算灵敏度 \(\Delta\) - 每到 \(t = 2^m\) 时通过 FFT 批量计算下一批 \(t\) 个 \(L\) 的系数和 \(Lz\) 的乘积 - 采样高斯噪声 \(z_s \sim \mathcal{N}(0, C_{\varepsilon,\delta}^2 \Delta^2)\) - 输出 \(S_t + (Lz)_t\)

实验关键数据¶

主实验：算法方差比较¶

算法	方差 \(\mathbb{V}(\mathcal{M}(X_t))\)	时间	空间	平滑	无界
二叉树	\(O(\log t \cdot \log n)\)	\(O(t)\)	\(O(\log t)\)	否	否
混合二叉树	\(O(\log^2 t + \log t)\)	\(O(t)\)	\(O(\log t)\)	否	是
平滑二叉树	\(O((\log n + \log\log n)^2)\)	\(O(t)\)	\(O(\log t)\)	是	否
Sqrt 矩阵	\(O(\log t \cdot \log n)\)	\(O(n\log n)\)	\(O(n)\)	是	否
Algorithm 1	\(O(\log^{2+2\alpha} t)\)	\(O(t\log t)\)	\(O(t)\)	是	是

消融/实际性能比较¶

参数配置	\(t=2^{12}\) 时方差比(vs Sqrt)	\(t=2^{24}\) 时方差比	说明
\(\delta=0\)	~1.3×	~1.4×	最快但误差稍大
\(\delta=-\gamma\)	~1.1×	~1.2×	中等
\(\delta=-6\gamma/5\)	~1.15×	~1.1×	\(t>2^{20}\) 后最优
Algorithm 2 (近似)	与 Algorithm 1 不可区分	与 Algorithm 1 不可区分	速度提升>5×

关键发现¶

对于 \(t\) 高达 \(2^{24}\)（约 1680 万），Algorithm 1 的方差始终不超过最优有界算法的 1.5 倍
Algorithm 2（近似版本）在 \(t \geq 2^{11}\) 后与精确版本几乎无差异，同时减少 80% 以上计算开销
混合机制（用 Algorithm 1 作为无界子组件）虽能达到精确 \(O(\log^2 t)\) 方差，但在 \(t\) 接近 \(2\) 的幂时误差剧烈波动

亮点与洞察¶

优雅地解决了持续隐私计数领域长期存在的"无界-平滑-最优"三难困境
从解析函数论角度切入矩阵分解问题，将代数问题转化为复分析问题
利用 Flajolet-Odlyzko 的经典渐近展开定理精确控制系数增长率——这种理论工具在隐私文献中很少见
开放问题引人深思：是否存在 LTToep 分解能达到精确 \(O(\log^2 n)\) 方差？

局限与展望¶

空间复杂度 \(O(t)\) 高于二叉树方法的 \(O(\log t)\)，不适合极长流
方差为 \(O(\log^{2+2\alpha} t)\) 而非最优的 \(O(\log^2 t)\)，尽管实际差异极小
仅讨论加法高斯噪声机制，未考虑其他噪声类型
作者猜测不存在 LTToep 分解能达到精确 \(O(\log^2 t)\)，但未能证明

评分¶

新颖性: ⭐⭐⭐⭐⭐ 从复分析角度解决组合优化问题，理论贡献优雅
实验充分度: ⭐⭐⭐⭐ 数值实验精确展示了理论结果，但无实际应用验证
写作质量: ⭐⭐⭐⭐⭐ 理论严谨但行文清晰，技术概览部分直觉解释极好
价值: ⭐⭐⭐⭐ 解决了重要理论问题，对大规模隐私系统部署有实际意义