Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting

技术摘要：纯 DP 连续计数中任意实矩阵分解的代价

问题陈述
本文研究了纯 $\epsilon$-差分隐私（DP）下的连续计数问题。在此设定下，机制必须在发布长度为 $n$ 的数据流的每一个前缀和时，同时保护个体更新的隐私。该工作负载由下三角前缀和矩阵 $T_n$ 表示，其中 $T_n(i, j) = 1$ 当且仅当 $j \le i$，否则为 $0$。

研究重点是**矩阵机制（matrix mechanism）**类，其中 $T_n$ 被分解为 $T_n = LR$。独立拉普拉斯噪声被添加到变换后的流 $Rx$中，前缀答案通过$L$进行重构。在具有单位$\ell_1$相邻性的纯$\epsilon$-DP 下，机制的敏感性由 $\|R\|_{1 \to 1}$（即 $R$ 的最大 $\ell_1$ 列范数）决定。本文研究了两种特定的分解代价，它们决定了所得机制的平均和最大每坐标平方误差：

1. $c_F(T_n) = \inf_{T_n=LR} \frac{\|L\|_F}{\sqrt{n}} \|R\|_{1 \to 1}$
2. $c_2(T_n) = \inf_{T_n=LR} \|L\|_{2 \to \infty} \|R\|_{1 \to 1}$

此前，Arkhipov 和 Kalinin 已经建立了这些代价的 $(\log n)^{3/2}$ 阶上界，并证明了对于元素限制在 $\{0, 1\}$ 中的因子，该下界同样成立。然而，他们留下了一个开放性问题：对于任意实因子（允许有符号、稠密以及具有任意有限内维度的矩形矩阵），该下界是否仍然成立。

方法论
本文通过一种基于 $p$-核性（$p$-nuclearity） 的几何与泛函分析方法解决了这一开放问题。证明架构包含三个主要步骤：

1. 聚合列宽估计： 作者推导了聚合列宽 $D_k(T_n)$ 的下界，其定义为 $T_n$ 的各列到任何 $k$ 维子空间的平方欧几里得距离之和。他们证明了在低秩范围 $1 \le k \le n/16$ 内，$D_k(T_n) \asymp n^{3/2} k^{-1/2}$。这是通过证明：若一个子空间过于接近超过一半的嵌套后缀指示函数，则会违反贝塞尔不等式（Bessel's inequality）来建立的。

2. 逼近空间转换： 本文利用算子理想理论中的经典结果（特别是 Pietsch 以及 Hinrichs–Pietsch 的工作），将聚合宽度与 $p$-核幂（$p$-nuclear power） $n_p(A)$ 联系起来。对于矩阵 $A$，$n_p(A)$ 是通过在所有有限秩一分解 $A = \sum u_q v_q^T$ 上取 $\sum (\|u_q\|_2 \|v_q\|_1)^p$ 的下确界来定义的。作者提供了一个定量的有限维证明，表明 $n_p(A)$ 被加权后的聚合宽度之和所限制。

3. 临界指数分析： 作者分析了 $n_p(T_n)$ 在临界指数 $p = 2/3$ 处的行为。在此处，由宽度估计导出的级数变为调和级数，从而产生 $n \log n$ 阶的下界。通过应用 Hölder 不等式，该 $p$-核界被转移到分解代价 $c_F(T_n)$ 和 $c_2(T_n)$ 上，将 $n \log n$ 项转化为所需的 $(\log n)^{3/2}$ 阶。

对于上界，本文采用经典的 Fenwick 区间分解（也称为二项树结构/Binary Indexed Tree 结构）来构造能够达到匹配上界的显式因子 $L$ 和 $R$。

核心贡献与结果

• 主定理 (Theorem 1.1)： 本文证明了对于具有任意有限内维度的任意实因子，分解代价满足：
  $$c(\log(n+1))^{3/2} \le c_F(T_n) \le c_2(T_n) \le C(\log(n+1))^{3/2}$$
  这证实了 $(\log n)^{3/2}$ 的阶数是矩阵机制类的固有属性，无论是否存在符号、稀疏性或方阵限制。

• 优化的误差阶 (Corollary 1.2)： 因此，在纯 $\epsilon$-DP 拉普拉斯矩阵机制类中，优化的最大和平均平方误差均为 $\Theta(\epsilon^{-2} \log^3(n+1))$。这填补了该特定矩阵机制类已知上界与下界之间的渐近差距。

• 固定-$p$ 相图 (Theorem 1.3)： 本文刻画了所有 $0 < p < 1$ 范围内 $n_p(T_n)$ 的 $p$-核幂，揭示了在 $p = 2/3$ 处的相变：

  • $n_p(T_n) = \Theta(n)$ 对于 $0 < p < 2/3$
  • $n_p(T_n) = \Theta(n \log n)$ 对于 $p = 2/3$
  • $n_p(T_n) = \Theta(n^{3p/2})$ 对于 $2/3 < p < 1$
    这些界限中的常数在 $p$ 方面不是一致的，并且在 $p \to 2/3$ 或 $p \to 1$ 时会发散。

• 上界： 本文提供了一个自洽的证明，表明 Fenwick 区间分解在整个相图中实现了与 $p$-核幂匹配的上界。

意义与声明

本文明确将其贡献定位为解决 Arkhipov 和 Kalinin 提出的关于将下界从二进制因子扩展到矩阵机制框架内任意实因子的特定开放问题的研究。

• 范围限制： 作者强调，其结果仅限于 纯 $\epsilon$-DP 拉普拉斯矩阵机制类。他们并不声称为一般的连续计数机制（包括非矩阵或交互式机制）提供下界，也不讨论近似-DP 敏感性或坐标间的期望最大值（这些由不同的泛函控制）。
• 理论性质： 该工作是纯理论性的，侧重于渐近阶和矩阵分解的几何学。它并未提出新的算法、经验评估或学习理论应用。
• $p$-核性的作用： 本文强调，误差阶中额外的 $\sqrt{\log n}$ 因子（相对于欧几里得敏感性的 $\log n$ 基准）是由于 $\|R\|_{1 \to 2}$ 与 $\|R\|_{1 \to 1}$ 之间的混合范数间隙造成的。这种间隙通过 $p < 1$ 时的 $p$-核阻碍得到了体现，而在该情形下，标准的基于范数的下界代理（其上限被限制在 $\log n$）会失效。

总而言之，本文证明了当限制在具有任意实因子的矩阵机制内时，$(\log n)^{3/2}$ 代价是纯 $\epsilon$-DP 连续计数的根本极限，解决了关于符号抵消是否能改进二进制因子下界的开放性问题。