技术摘要：效用优化局部差分隐私下离散分布估计的基础极限

1. 问题定义

本文研究了在效用优化局部差分隐私 (Utility-Optimized Local Differential Privacy, ULDP) 约束下的离散分布估计问题。在此设定下，服务器试图基于 $n$ 个客户端的数据来估计一个未知概率分布 $P$，其定义域为 $\mathcal{X} = [w]$。每个客户端 $i$ 持有一个私有样本 $X_i \sim P$。

与标准的局部差分隐私 (LDP) 不同——标准 LDP 要求对所有输入值对都满足不可区分性——ULDP 承认只有一部分数据 $\mathcal{X}_S \subset \mathcal{X}$（大小为 $v$）是敏感的。剩余的非敏感数据 $\mathcal{X}_N = \mathcal{X} \setminus \mathcal{X}_S$ 可以更准确地披露。

• 敏感数据 ($\mathcal{X}_S$)： 必须满足标准的 $\epsilon$-LDP 保证。
• 非敏感数据 ($\mathcal{X}_N$)： 可以被映射到“可逆”输出，只要该机制满足特定的结构约束，即可完美揭示输入。

目标是刻画基础隐私-效用权衡 (Privacy-Utility Trade-off, PUT)，即渐近极小极大均方误差 (MSE) 每样本值，记作 $M^*(w, v, \epsilon)$。虽然之前的研究已经确立了阶数最优性（例如 $\Theta(1/n)$），但刻画 ULDP 下基础极限的精确前导常数仍然是一个悬而未决的问题。

2. 研究方法

作者采用了双管齐下的方法：通过逆向证明 (Converse Proof) 建立误差下界，以及通过一种新型机制设计进行可达性证明 (Achievability Proof)。

A. 逆向证明 (下界)

逆向证明确立了任何 ULDP 机制都无法实现的低于特定值的误差。它依赖于三个关键的分析框架：

1. 广义一致渐近克拉美-罗下界 (Generalized Uniform Asymptotic Cramér–Rao Lower Bound, CRLB)： 作者将此前用于标准 LDP 的一致渐近 CRLB 扩展到了通用的隐私估计问题。这涉及证明对于一类机制，渐近误差被分布空间上 Fisher 信息矩阵逆迹的上确界所限制。
2. 归约为极值 ULDP 机制： 正如极值 LDP 机制足以处理标准 LDP 一样，作者定义了一类新的极值 ULDP 机制。他们证明了所有 ULDP 机制都被这个较小的紧致极值机制集合所“降级”。这使得极小极大分析可以限制在这个特定的集合内，从而简化了优化过程。
3. 分布分解： 一种新颖的技术，根据 ULDP 约束的结构将数据分布 $P$ 分解为三个正交分量：
   • $\mathcal{X}_S$ 内部的相对概率。
   • $\mathcal{X}_N$ 内部的相对概率。
   • 敏感集 $\mathcal{X}_S$ 的总概率质量 $P(\mathcal{X}_S)$。
     下界被推导为分别估计这三个分量的 CRLB 之和。

B. 可达性证明 (上界)

为了匹配下界，作者提出了一类被称为效用优化块设计 (Utility-Optimized Block Design, uBD) 方案的机制。

• 机制构建： uBD 机制是标准块设计 (Block Design, BD) 机制（已知对 LDP 是最优的）应用于敏感数据的混合，并结合了对非敏感数据的特定处理。
  • 机制通过概率 $t_k$ 随机选择一个块设计参数 $k$。
  • 敏感输入通过选定的 BD 机制进行扰动。
  • 非敏感输入要么通过 BD 机制进行扰动，要么被直接映射到可逆输出（忠实地揭示输入）以最大化效用。
• 估计器设计： 作者利用了一个基于评分的线性估计器。通过将估计问题分解为逆向证明中识别出的三个分量，他们构建了一个使每个分量的 CRLB 饱和的估计器。该估计器序列被设计为是无偏且渐近最优的。

3. 核心贡献与结果

A. 基础极限的精确刻画

主要贡献在于完整刻画了最优的 PUT $M^*(w, v, \epsilon)$，包括精确的前导常数。最优误差由一个有限维的凹-凸鞍点优化问题的解给出：
$$M^*(w, v, \epsilon) = \sup_{\alpha \in [0,1]} \inf_{t \in \Delta_v} M(\alpha, t)$$
其中 $M(\alpha, t)$ 是代表分解后的三个组成部分之 CRLB 的三项之和（$M_1, M_2, M_3$）。

B. 特定情形下的闭式解

论文提供了特定情形下最优参数 $(\alpha^*, t^*)$ 的闭式解：

1. 情形 (a)： 当 $v=1$，或者当 $\epsilon$ 足够大（低隐私需求），或当 $v=2$ 且 $\epsilon$ 较小时。在这些情况下，最优策略退化为效用优化随机响应 (Utility-Optimized Randomized Response, uRR) 方案。本文首次证明了 uRR 在这些情形下是渐近最优的。
2. 情形 (b)： 当 $v \ge 4$ 且 $\epsilon$ 较小（高隐私需求）时。在此情形下，最优策略对应于使用单个块设计参数 $k^*$ 的简单 uBD 方案（具体而言，是一个 $t^*$ 在 $k^*$ 处为点质量的混合）。

C. uBD 的严格优越性

作者证明了先前提出的 ULDP 方案，如 uSS (Utility-Optimized Subset Selection)，在某些情形下（特别是情形 (b)）是次优的。uBD 方案实现的估计误差严格低于 uSS，确立了现有方法与基础极限之间的差距。

D. 实验验证

作者使用 2023 年美国社区调查 (ACS) 数据集，将 uBD 方案与基准方案（uRR, uHR, uSS, uOUE, uOLH）进行了对比评估。

• 结果： 在不同的隐私预算 ($\epsilon$) 和敏感集大小 ($v$) 下，uBD 方案始终优于所有基准方案。
• 中间情形： 在不存在闭式解的中间隐私情形中，数值优化显示最优混合比例 $t^*$ 收敛为一个两点分布（仅使用 $k=1$ 和 $k=2$ 的块设计），这表明仅混合两个块设计就足以接近最优。

4. 意义与主张

本文声称提供了 ULDP 下离散分布估计基础极限的首次完整刻画。其意义在于：

• 理论严谨性： 超越了阶数最优性，提供了精确的常数，解决了文献中关于 ULDP 精确性能极限的空白。
• 机制设计： 引入了 uBD 框架，通过利用极值机制的结构和分布分解，推广并改进了现有的 ULDP 机制。
• 最优性证明： 证明了 uRR 在特定情形下的最优性，并证明了先前已知最佳方案 (uSS) 在其他情形下的严格次优性。
• 分析工具： 开发的广义一致渐近 CRLB 和分布分解技术被视为通用的工具，可能适用于 ULDP 之外的其他隐私估计问题。

作者对未来的工作保持了谦逊的态度，指出推导中间隐私情形下的闭式解仍是一个开放性挑战，并建议将其扩展到其他损失函数（如 $\ell_p$ 损失、f-散度）以及实例最优性 (instance-optimality) 的设置。