技术摘要：尾部风险学习的隐私代价

1. 问题陈述

本文探讨了差分隐私 (DP) 如何影响条件风险价值 (CVaR) 的学习这一根本问题，CVaR 是一种用于优化罕见或高损失子群体性能的标准尾部风险泛函。

在标准经验风险最小化 (ERM) 中，目标是最小化平均损失。相比之下，CVaR 关注损失分布中最差的 $\tau$ 分数部分（其中 $\tau \in (0, 1]$ 为尾部质量）。研究指出的核心挑战在于，决定 CVaR 目标的样本恰恰是高损失的“尾部”样本。在许多应用中，这些样本对应于罕见、非典型或少数群体的案例。因此，鲁棒性（关注尾部）与隐私（保护个体记录）的要求在这些相同的观测值上发生了冲突。

本文旨在刻画差分隐私下的最小最大超额 CVaR 风险。具体而言，它提出：私有 CVaR 学习的最佳收敛速率是多少？隐私参数 $\epsilon$ 如何与尾部质量 $\tau$ 和样本量 $n$ 相互作用？

2. 方法论与框架

作者结合了敏感性分析、最小最大下界构造以及模块化归约，将 CVaR 学习与既有的私有随机凸优化 (SCO) 理论联系起来。

2.1 敏感性分析

分析首先确立了经验 CVaR 目标的精确单条记录敏感性。

• 对于有界损失 $\ell \in [0, B]$，更改数据集中的单条记录，其最小化的经验 CVaR 变化量至多为 $B \min\{1, 1/(n\tau)\}$。
• 关键在于，敏感性按 $1/(n\tau)$ 而非 $1/n$ 缩放。这是因为经验 CVaR 目标实际上仅对 $n\tau$ 个具有信息量的尾部记录进行平均，赋予每个记录 $1/(n\tau)$ 的权重。
• 这一敏感性计算决定了差分隐私所需的噪声规模，表明隐私层面的“有效样本量”并非 $n$，而是 $n\tau$。

2.2 风险分解

本文提出将私有超额 CVaR 风险分解为两个截然不同的组成部分：

1. 普通尾部风险统计误差：从 $n$ 个样本中估计尾部风险所固有的误差，其规模与有效样本量 $n\tau$ 相关。
2. 隐私代价：由差分隐私引入的额外误差，其规模与有效私有尾部样本量 $\epsilon n\tau$ 相关。

2.3 模块化归约

对于凸 Lipschitz 学习，作者采用了一种模块化方法：

• 上界：他们通过 Rockafellar-Uryasev 提升目标函数，将私有 CVaR 问题归约为标准的私有 SCO 问题。这将 CVaR 最小化转化为提升参数空间 $(w, \eta)$ 上的凸优化问题。
• 下界：他们利用尾部样本转移定理。该定理将一个具有 $m$ 个样本的普通私有 SCO 问题嵌入到一个具有 $n$ 个样本的 CVaR 问题中，其中 $m \approx n\tau$。这证明了任何关于 $m$ 个样本的私有 SCO 的困难性结果，立即转化为关于具有 $n\tau$ 个信息记录、$n$ 个样本的私有 CVaR 的困难性结果。

3. 主要贡献与结果

3.1 标量估计

对于私有估计标量随机变量 $Z \in [0, B]$ 的 CVaR 问题，本文在纯 DP（以及小 $\delta$ 下的近似 DP）下确立了完整的最小最大速率：
$$\Theta\left( B \min\left\{ 1, \frac{1}{\sqrt{n\tau}} + \frac{1}{\epsilon n\tau} \right\} \right)$$

• 项 $1/\sqrt{n\tau}$ 代表统计误差。
• 项 $1/(\epsilon n\tau)$ 代表隐私代价。
• 意义：该结果证明隐私惩罚按 $1/(\epsilon n\tau)$ 缩放，而非 $1/(\epsilon n)$。即使 VaR 阈值已知，下界依然成立，从而将难度隔离为尾部平均值的私有估计。

3.2 有限类学习

对于大小为 $M$ 的有限假设类，完整的最小最大速率为：
$$\Theta\left( B \min\left\{ 1, \sqrt{\frac{\log(2M)}{n\tau}} + \frac{\log(2M)}{\epsilon n\tau} \right\} \right)$$

• 普通统计项按 $\sqrt{\log M / (n\tau)}$ 缩放。
• 隐私项按 $\log M / (\epsilon n\tau)$ 缩放。
• 这证实了统计项和隐私项的有效样本量均由尾部质量 $\tau$ 决定。

3.3 凸 Lipschitz 学习

对于直径为 $D$ 的欧几里得集上具有 Lipschitz 常数 $G$ 的凸 Lipschitz 损失：

• 上界：利用提升凸公式和标准私有 SCO 算法，私有项按以下比例缩放：
  $$\tilde{O}\left( \frac{(GD + B)\sqrt{d}}{\epsilon n\tau} \right)$$
  （其中 $\tilde{O}$ 隐藏了多对数因子）。
• 下界：通过尾部样本转移定理，本文证明了匹配的下界（忽略对数因子）：
  $$\tilde{\Omega}\left( \min\{B, GD\} \min\left\{ 1, \frac{1}{\sqrt{n\tau}} + \frac{\sqrt{d}}{\epsilon n\tau} \right\} \right)$$
• 相变：仅当有效私有尾部样本量主导模型复杂度时，即 $\epsilon n\tau \gg \sqrt{d}$，非平凡的私有尾部风险学习才成为可能。

3.4 敏感性扩展

本文将敏感性分析扩展到一般的包络有界相干风险。对于具有对偶密度包络有界于 $\kappa$ 的相干风险，其单条记录敏感性为 $B \min\{1, \kappa/n\}$。对于 CVaR，$\kappa = 1/\tau$。作者认为，尽管最小最大速率是专门针对 CVaR 证明的，但敏感性机制表明，其他具有有界包络的相干风险也具有类似的隐私代价结构。

4. 意义与主张

本文声称识别了隐私 - 尾部风险前沿，并解决了私有 CVaR 学习的最小最大速率。其主要贡献如下：

1. 有效样本量的识别：该工作证明，在尾部风险学习中，统计估计和隐私保护的相关样本量是 $n\tau$，而非 $n$。隐私代价与信息性尾部记录的数量成反比。
2. 分解的完备性：对于标量和有限类设置，本文提供了将误差分解为统计项和隐私项的“封闭”形式，表明隐私代价是固有的且不可避免的。
3. 模块化：结果将 CVaR 的具体几何特性（$1/\tau$ 因子）与私有凸优化的一般几何特性分离开来。这使得现有的私有 SCO 结果可以直接应用于 CVaR，只需对样本量进行简单的重缩放。
4. 与分位数估计的区别：本文阐明了私有 CVaR 学习不同于私有分位数估计。即使 VaR 阈值已知，私有估计尾部平均值的难度依然存在，这是由尾部记录的敏感性驱动的。

作者得出结论：逆尾部质量因子 $1/\tau$ 是尾部风险学习的固有隐私代价。结果表明，在差分隐私下保护罕见、高影响事件（尾部）所付出的代价与这些事件的稀有程度 ($1/\tau$) 呈线性关系，从根本上改变了与平均风险学习相比的样本复杂度要求。