Universal Shuffle Asymptotics, Part III: Dominant-Block Quotient Geometry and Hybrid Gaussian--Compound-Poisson Limits in Finite-Alphabet Shuffle Privacy

1. 研究背景与问题 (Problem)

背景：
洗牌模型（Shuffle Model）是本地差分隐私（LDP）与集中式隐私之间的中间模型，通过引入一个可信的洗牌器（Shuffler）来增强隐私保护。该系列论文旨在建立洗牌实验（Shuffle Experiments）的完整渐近理论。

• 第一部分 [1]：建立了在固定全支撑（full-support）且概率远离零的“密集”区域下，相邻洗牌实验收敛到高斯极限（LAN/GDP）的理论。
• 第二部分 [2]：揭示了当局部随机化器变得高度集中（即某些输出概率趋于零）时，高斯极限失效，系统进入临界泊松、Skellam 或多变量复合泊松区域。

核心问题：
前两部分的理论存在结构性缺口。第二部分仅处理了特殊的“两个主导块不相交”的情况。然而，在更一般的有限字母表设置中，存在以下未解决的问题：

1. 主导块重叠：两个相邻假设下的主导输出集合（Dominant Sets）可能重叠。
2. 主导块大小任意：主导块的大小可能大于 2，且可能具有不同的结构。
3. 混合几何结构：当主导块既包含高斯分量又包含稀有（Rare）分量时，如何描述其联合极限？
4. 隐私曲线收敛性：在强边界（Strong Boundary）情况下，仅凭投影后的跳跃极限是否足以确定完整的隐私曲线？

本文旨在填补这些缺口，建立适用于一般有限字母表的**主导块商几何（Dominant-Block Quotient Geometry）**理论，并推导混合高斯 - 复合泊松极限。

---

2. 方法论 (Methodology)

本文采用统计实验理论（Statistical Experiments）、Le Cam 距离、特征函数展开以及泊松近似工具。核心方法论包括：

2.1 主导块商几何 (Dominant-Block Quotient Geometry)

作者定义了一个几何分解框架，将洗牌直方图（Histogram）分解为两个正交部分：

• 主导切空间 (Dominant Tangent Space, $M$)：由主导输出集合 $D_0$ 和 $D_1$ 生成的线性空间。在此空间上，统计量表现为高斯分布。
• 商空间 (Quotient Space, $M^\perp$)：正交于主导切空间。在此空间上，稀有输出（Rare Outputs）表现为复合泊松过程（Compound Poisson Process）。

通过正交投影算子 $\Pi_G$（投影到 $M$）和 $\Pi_J$（投影到 $M^\perp$），将原始统计量 $S_n$ 分解为：
$$S_n = (\Pi_G \bar{H}_n, \Pi_J \bar{H}_n)$$
其中 $\bar{H}_n$ 是中心化的直方图。

2.2 混合极限定理 (Hybrid Limit Theorem)

利用 Lévy-Khintchine 公式，证明了在相邻假设下，统计量收敛于一个混合实验：

• 高斯因子：$G \sim N(0, \Sigma)$，在两个假设下分布相同（无位移）。
• 跳跃因子：$J$ 为复合泊松随机向量，其 Lévy 测度由稀有输出的强度决定。
• 位移：相邻假设的差异完全由商空间上的确定性位移 $\Delta = \Pi_J(\mu_1 - \mu_0)$ 承载。

2.3 隐私曲线分析技术

• Blackwell 等价性：通过构造辅助实验，利用 Blackwell 定理将完整实验的隐私曲线与投影后的实验联系起来。
• 条件平滑 (Conditional Smoothing)：在主导块内部，通过替换少量“外来”消息（来自对立群体的稀有消息）为“原生”主导消息，利用多项式分布的局部中心极限定理来估计总变差距离（TV）。
• 边界分析：针对强边界情况（少数群体大小有界），构造反例证明投影极限不足以描述完整隐私曲线。

---

3. 主要贡献与结果 (Key Contributions & Results)

3.1 一般 $k$-主导 Lévy-Khintchine 极限定理 (Theorem 3.1)

这是本文的核心成果。它证明了在一般有限主导块（允许重叠、任意大小）下，相邻洗牌实验收敛于混合实验 $(G, J)$ 与 $(G, J+\Delta)$。

• 高斯部分：由主导块的协方差矩阵 $\Sigma$ 决定，在两个假设下不变。
• 跳跃部分：由稀有输出的强度 $\alpha_b(y)$ 和投影向量 $j_{b,y}$ 决定。
• 位移 $\Delta$：
  • 如果 $D_0 \cap D_1 = \emptyset$（不相交），$\Delta \neq 0$，表现为泊松位移。
  • 如果 $D_0 \cap D_1 \neq \emptyset$（重叠），$\Delta = 0$，极限分布在两个假设下相同（隐私在极限意义下完全消失，但在有限 $n$ 下仍有隐私）。

3.2 收敛速率与总变差界

• 投影块的收敛：在商空间 $M^\perp$ 上，统计量收敛到复合泊松极限的总变差距离为 $O(n^{-1})$。
• 完整实验的收敛：完整实验收敛到混合极限的总变差距离为 $O(n^{-1/2})$。
  • 定理 7.2：通过构造二项式加伯努利的反例，证明了 $O(n^{-1/2})$ 的速率是尖锐的（Sharp），无法在一般情况下改进。
  • 定理 7.3：提出了一个兼容性条件（Cross-split law compatibility），即当对立群体的交叉分布与原生主导分布足够接近时，速率可恢复为更优的 $O(n^{-1})$。

3.3 边界 Berry-Esseen 定理 (Theorem 8.1)

证明了当临界参数 $c \to 0$ 时，临界泊松位移实验（Poisson-shift）与高斯位移实验（Gaussian-shift）之间的 Le Cam 距离为 $O(c)$。这表明在临界点附近，泊松极限平滑地过渡到高斯极限，且隐私曲线也随之连续过渡。

3.4 强边界障碍 (Strong-Boundary Obstruction)

命题 6.1 指出，如果没有额外的结构假设（如少数群体主导块被多数群体吸收），仅凭投影后的跳跃极限不能确定完整的隐私曲线。

• 反例：构造了一个重叠主导块且少数群体大小有界的场景。在极限下 $\Delta=0$ 且 $\nu=0$，导致极限隐私曲线为 0；但在有限 $n$ 下，由于少数群体内部几何结构的保留，隐私曲线仍显著大于 0（$\ge 1/2$）。这揭示了投影方法在强边界下的局限性。

---

4. 意义与影响 (Significance)

1. 理论完整性：本文完成了有限字母表洗牌隐私的弱极限理论，建立了从“全支撑高斯”到“稀疏复合泊松”再到“混合高斯 - 泊松”的完整三阶段普适性图景（Three-regime universality picture）。
2. 几何洞察：引入了“主导块商几何”这一新概念，清晰地分离了洗牌机制中的确定性高斯分量（主导块）和随机跳跃分量（稀有块），为理解复杂隐私机制提供了新的几何视角。
3. 隐私曲线精度：不仅给出了极限分布，还给出了隐私曲线收敛的精确速率和条件。特别是揭示了 $O(n^{-1/2})$ 速率的普遍性和 $O(n^{-1})$ 速率恢复的特定条件，这对实际隐私预算的评估至关重要。
4. 反直觉发现：揭示了在重叠主导块情况下，极限分布可能相同（$\Delta=0$），但这并不意味着有限样本下的隐私消失。这强调了在分析隐私时，必须考虑有限样本的“未平滑”几何结构，不能仅依赖渐近极限。
5. 未来方向：为处理更复杂的非相邻假设、无限字母表以及未捆绑（unbundled）多消息机制的临界理论奠定了基础。

总结

这篇论文是洗牌隐私渐近理论的重要里程碑。它通过引入商几何分解，成功统一了高斯和复合泊松极限，并精确刻画了两者之间的过渡机制及收敛速率。同时，它通过严谨的反例指出了渐近理论在强边界情况下的局限性，为未来的隐私分析提供了更细致和准确的理论工具。