Universal Shuffle Asymptotics, Part II: Non-Gaussian Limits for Shuffle Privacy -- Poisson, Skellam, and Compound-Poisson Regimes

Each language version is independently generated for its own context, not a direct translation.

这篇论文是《通用洗牌渐近理论》系列的第二部分，主要探讨了一个非常有趣且反直觉的现象：当隐私保护强度调整到某个“临界点”时，数据的隐私保护行为会发生突变，不再遵循我们熟悉的“正态分布”（钟形曲线），而是变成了像“泊松分布”或“斯凯姆分布”那样充满跳跃和随机性的模式。

为了让你轻松理解，我们可以把这篇论文的研究对象想象成一场**“匿名投票大会”**。

1. 背景：什么是“洗牌模型”？

想象有一个大型会议，有 $n$ 个人（用户）。每个人手里有一个秘密（比如“是”或“否”）。

本地随机化（Local Randomizer）： 每个人在把秘密告诉别人之前，会先在自己的小房间里扔一枚硬币。如果硬币是正面，他就如实说；如果是反面，他就随机瞎编一个。这叫“加噪”，目的是保护隐私。
洗牌（Shuffle）： 所有人把写好的纸条扔进一个巨大的、不透明的搅拌机（洗牌器）里。搅拌机把纸条彻底打乱，然后随机吐出来。
结果： 分析员只能看到一堆乱序的纸条，不知道谁说了什么，但能统计出“是”和“否”的大致比例。

第一部分（Part I）的研究结论是： 如果每个人扔硬币的“作弊率”（隐私参数 $\epsilon$ ）保持在一个比较稳定的水平，那么当人数 $n$ 非常多时，这堆纸条的统计结果会非常平滑，像**正态分布（高斯分布）**一样。这意味着我们可以用非常成熟的数学工具来预测隐私泄露的风险。

2. 第二部分的核心发现：临界点的“突变”

这篇论文（Part II）问了一个新问题：如果我们随着人数 $n$ 的增加，故意让每个人“作弊”的概率变得非常非常小（但还没小到完全诚实），会发生什么？

这就好比：

普通情况（亚临界）： 每个人都会偶尔撒个小谎，谎言很多但都很小。结果像平静的湖面，波纹是平滑的（高斯分布）。
临界情况（本文重点）： 我们调整参数，让每个人撒谎的概率变得极低，大概只有 $1/n $。这意味着在$ n$ 个人里，大概只有几个人会撒谎，而且这几个人一旦撒谎，就会造成巨大的“跳跃”。

论文发现，在这个临界点上，世界变了：

不再是平滑的波浪，而是离散的跳跃： 统计结果不再像钟形曲线，而是像泊松分布（Poisson）。这就像你不再看平静的湖面，而是看暴雨中落下的雨滴。雨滴数量很少，但每一滴落下的声音（数据跳跃）都很清晰、很突兀。
新的数学怪兽： 对于更复杂的情况（比如不止两个选项），这种分布变成了斯凯姆分布（Skellam，两个泊松分布的差）或者复合泊松分布。

3. 生动的比喻：雨滴与海浪

为了理解为什么这很重要，我们可以用两个比喻：

比喻一：海浪 vs. 雨滴

高斯（正态）世界（Part I）： 就像海浪。成千上万个小水珠（微小的隐私泄露）汇聚在一起，形成了平滑、可预测的波浪。你可以用简单的公式算出波浪有多高。
泊松/斯凯姆世界（Part II）： 就像暴雨中的雨滴。在这个临界点，大部分人都很诚实（像没下雨），只有极少数人“掉链子”（撒谎）。
- 如果没人撒谎，数据就是完美的。
- 如果只有 1 个人撒谎，数据就会突然跳变一下。
- 这种**“要么没事，要么大跳”**的特性，就是泊松分布的核心。

比喻二：安检门

想象你在过安检。

普通模式： 每个人身上都带一点点金属（微小的隐私泄露），安检仪会显示一个稳定的读数。
临界模式： 绝大多数人身上完全干净，但偶尔（概率极低）会有一个人带了一把大锤子。
- 如果没人带锤子，读数归零。
- 如果有人带锤子，读数直接爆表。
- 这时候，你不能用“平均风险”来评估，因为那把大锤子（宏观跳跃）决定了整个系统的风险。

4. 论文解决了什么具体问题？

这篇论文就像是一个**“临界状态导航仪”**，它告诉我们在什么情况下会发生这种突变，以及突变后该怎么算账：

发现了“地板效应”（The Floor）：
- 在普通模式下，如果你把隐私保护设得足够强（ $\epsilon$ 很大），泄露风险理论上可以无限接近于 0。
- 但在临界模式下，论文发现了一个**“无法消除的底线”**。因为只要有人撒谎（哪怕概率极低），就存在一种可能性：那个撒谎的人恰好是我们要保护的目标，而其他人都是诚实的。这种“支持不匹配”导致隐私风险永远无法降到 0，就像地板上有一层擦不掉的灰尘。
提供了精确的“地图”：
- 论文给出了三种状态的完整地图：
  - 亚临界（Sub-critical）： 人多、谎言多但小 $\rightarrow$ 高斯/正态分布（平滑）。
  - 临界（Critical）： 人多、谎言极少但大 $\rightarrow$ 泊松/斯凯姆分布（跳跃，有底线）。
  - 超临界（Super-critical）： 谎言太多或太强 $\rightarrow$ 隐私彻底崩溃（完全可区分）。
通用性（Universality）：
- 不管你是只有“是/否”两个选项，还是有几十个选项，只要进入这个临界状态，规律都是一样的。这就像物理学家发现万有引力定律一样，他们发现了隐私保护在临界状态下的“万有引力”。

5. 这对我们意味着什么？

对于设计隐私保护系统（比如苹果、谷歌收集用户数据）的工程师来说，这篇论文是一个重要的警告和指南：

不要盲目调整参数： 如果你为了减少误差而把隐私参数调得太高（接近临界点），你以为只是稍微增加了一点风险，但实际上系统可能突然从“平滑模式”跳到了“跳跃模式”，导致隐私保护出现意想不到的硬性底线（即无论怎么算，都有一定概率泄露）。
需要新的数学工具： 在临界点附近，以前用的那些基于“正态分布”的公式不管用了，必须用这篇论文提供的“泊松/斯凯姆”新公式来重新计算风险。

总结

简单来说，这篇论文告诉我们：在隐私保护的“临界地带”，世界不是平滑的，而是充满随机跳跃的。 就像在平静的湖面上突然下起了暴雨，雨滴（数据泄露）虽然少，但每一滴都清晰可见，且永远无法完全消除。作者通过严密的数学推导，为我们绘制了这张从“平滑”到“跳跃”再到“崩溃”的完整风险地图。

Each language version is independently generated for its own context, not a direct translation.

这是一篇关于洗牌模型（Shuffle Model）中差分隐私（DP）渐近理论的学术论文，题为《通用洗牌渐近性，第二部分：洗牌隐私的非高斯极限——泊松、Skellam 和复合泊松机制》。作为该系列第一部分（主要讨论高斯/高斯差分隐私 GDP 极限）的续篇，本文专注于临界区域（Critical Regime），即当局部隐私参数 $\varepsilon_0$ 随用户数量 $n$ 增长，导致经典中心极限定理（CLT）失效，而极限分布呈现非高斯特征的情况。

以下是对该论文的详细技术总结：

1. 研究问题与背景

背景：在洗牌模型中，本地随机化器（Local Randomizer）生成的消息经过匿名化洗牌后，隐私保护能力通常会得到放大（Amplification）。第一部分证明了在局部随机化器固定且支持集远离零的“次临界”区域，隐私损失渐近服从高斯分布（GDP）。
核心问题：在实际应用中，为了降低估计方差，局部隐私参数 $\varepsilon_0(n)$ 往往随 $n$ 增大。当 $\varepsilon_0(n)$ 增长到使得局部翻转概率约为 $O(1/n)$ 时（即 $e^{\varepsilon_0(n)} \sim c^2 n$ ），局部随机化器产生的“错误”变得极其稀疏但宏观影响显著。此时，经典的 Lindeberg 条件失效，隐私损失不再服从高斯分布，而是表现出宏观跳跃（Macroscopic Jumps）。
目标：刻画这一临界区域的极限行为，建立精确的非高斯极限理论（Le Cam 距离收敛），并推导显式的隐私曲线（Privacy Curves）。

2. 方法论与框架

实验等价性（Le Cam Distance）：论文采用 Le Cam 距离作为衡量两个统计实验（邻域数据集 $k$ 与 $k+1$ ）相似性的标准。通过证明洗牌后的统计量在总变差（Total Variation, TV）距离下收敛到特定的极限分布，从而确立实验层面的等价性。
缩放参数：定义关键缩放参数 $a_n = e^{\varepsilon_0(n)} / n$ $a_{n} = e^{ε_{0} (n)} / n$ 。
- 次临界： $a_n \to 0$ （高斯极限，见第一部分）。
- 临界： $a_n \to c^2 \in (0, \infty)$ （本文重点）。
- 超临界： $a_n \to \infty$ （隐私失效）。
技术工具：
- 泊松逼近：利用二项分布到泊松分布的总变差界限（Chen-Stein 方法变体）。
- Le Cam 距离界：通过 TV 距离控制 Le Cam 距离。
- 特征函数与 Lévy-Khintchine 分解：用于分析复合泊松极限。
- 隐私曲线（Privacy Curve）：基于 Neyman-Pearson 引理，计算 $\delta(\varepsilon)$ 的显式级数形式。

3. 主要贡献与结果

3.1 二元随机响应（Binary Randomized Response）的临界极限

针对二元输入（0 或 1），论文根据数据集中 1 的比例 $\pi = k/n$ 区分了两种极限情况：

泊松移位极限（Poisson-shift Limit）：
- 场景：当 $\pi \to 0$ 或 $\pi \to 1$ （即边界组成，如全 0 数据集与含一个 1 的数据集）。
- 结果：极限实验收敛到 $(P_\infty, Q_\infty) = (\text{Poi}(\lambda), 1 + \text{Poi}(\lambda))$ ，其中 $\lambda = c^{-2}$ 。
- 隐私特征：存在一个非零的 $\delta$ -floor（ $\delta$ -地板）。由于极限分布 $Q_\infty$ 在 0 处概率为 0，而 $P_\infty$ 在 0 处概率为 $e^{-\lambda}$ ，导致对于任意 $\varepsilon$ ，隐私损失 $\delta(\varepsilon) \ge e^{-\lambda}$ 。这意味着即使 $\varepsilon \to \infty$ ，隐私也无法完全消除，这是高斯极限中不存在的现象。
- 收敛速率：Le Cam 距离为 $O(n^{-1})$ 。
Skellam 移位极限（Skellam-shift Limit）：
- 场景：当 $\pi \in (0, 1)$ （即内部组成，0 和 1 均占一定比例）。
- 结果：极限实验收敛到 $(P_\infty, Q_\infty) = (\text{Skellam}(\lambda_0, \lambda_1), 1 + \text{Skellam}(\lambda_0, \lambda_1))$ 。Skellam 分布是两个独立泊松变量之差。
- 隐私特征：由于 Skellam 分布在整数集上具有全支撑（Full Support），不存在 $\delta$ -floor。隐私曲线随 $\varepsilon$ 增大可趋于 0。
- 连续性：当 $\pi \to 0$ 或 $1 $时，Skellam 极限平滑过渡到泊松极限，但在边界处会出现$ \delta$-floor 的突变。

3.2 一般有限字母表（General Finite Alphabets）

稀疏误差临界机制（Sparse-error Critical Regime）：允许输出字母表 $Y$ 大于 2，且局部随机化器在主导输出上概率趋于 1，非主导输出概率为 $O(1/n)$ 。
复合泊松极限（Compound-Poisson Limit）：
- 证明了中心化的发布直方图收敛到多元复合泊松分布（或独立泊松向量）。
- 极限实验形式为 $(P_\infty, Q_\infty) = (H_\infty, H_\infty + e)$ ，其中 $H_\infty$ 是复合泊松随机向量， $e$ 是移位向量。
- 给出了显式的隐私曲线级数公式，并证明了在正则条件下收敛速率为 $O(n^{-1})$ 。

3.3 混合高斯/复合泊松极限（Hybrid Limit）

场景：当主导输出的概率不坍缩到单点，而是分裂为两个主导输出（概率为 $O(1)$ ），同时存在稀疏误差。
结果：提出了高斯/复合泊松混合极限。
- 主导块（Dominant Block）的波动服从高斯分布（ $\sqrt{n}$ 尺度）。
- 稀疏误差块（Rare-jump Block）服从复合泊松分布（ $O(1)$ 尺度）。
- 极限分布具有 Lévy-Khintchine 结构： $G + J$ ，其中 $G$ 是高斯项， $J$ 是复合泊松项。
- 注意：在此混合情形下，由于高斯分量在两个假设下是相同的（无移位），隐私主要由复合泊松分量决定。论文通过投影技术证明了隐私曲线的收敛性。

4. 三阶段相图（Three-Regime Synthesis）

论文结合第一部分，构建了洗牌隐私的完整相图：

次临界（Sub-critical, $a_n \to 0$ ）：高斯/GDP 极限。隐私损失由大量微小增量累积，无宏观跳跃。
临界（Critical, $a_n \to c^2$ ）：非高斯极限（泊松/Skellam/复合泊松）。隐私损失由 $O(1)$ $O (1)$ 个宏观跳跃主导。
- 边界组成：泊松极限，存在 $\delta$ -floor。
- 内部组成：Skellam 极限，无 $\delta$ -floor。
超临界（Super-critical, $a_n \to \infty$ ）：隐私失效。两个邻域分布渐近可区分（TV 距离趋于 1）， $\delta(\varepsilon) \to 1$ 。

5. 与现有工作的对比与意义

对比现有界限：
- 现有的放大界限（如 Balle et al., Feldman et al.）通常基于“许多小贡献”的假设（高斯近似），在临界区域失效。
- 本文揭示了在临界区域，现有的基于 $n^{-1/2}$ 放大的界限无法捕捉到非零的 $\delta$ -floor，从而可能高估隐私保护能力。
理论意义：
- 填补了洗牌模型从局部隐私到全局隐私过渡中“非高斯”区域的理论空白。
- 引入了 Le Cam 距离下的精确收敛速率（ $O(n^{-1})$ ），超越了弱收敛（Weak Convergence）。
- 揭示了宏观跳跃（Macroscopic Jumps）对隐私曲线的根本性影响，特别是 $\delta$ -floor 的存在性。
实践指导：
- 为协议设计者提供了选择 $\varepsilon_0(n)$ 的指导：若需避免 $\delta$ -floor，应确保处于内部组成或次临界区域；若处于临界边界，必须接受 $\delta$ 的下界。
- 指出了在临界区域，隐私曲线不仅取决于 $\varepsilon$ ，还强烈依赖于数据组成的宏观参数 $\pi$ 。

6. 结论

本文通过严格的渐近分析，证明了在洗牌模型的临界参数设置下，隐私保护的极限行为由泊松过程主导，而非高斯过程。这一发现修正了传统的高斯近似直觉，揭示了在特定参数设置下隐私保护存在不可消除的“地板”（Floor），为差分隐私系统的参数选择和安全性评估提供了更精确的理论基础。