Not All Learnable Distribution Classes are Privately Learnable

技术摘要：“并非所有可学习的分布类都是可私有学习的”

问题陈述
本文探讨了统计学习理论与差分隐私（DP）交叉领域的一个根本性问题：在标准（非私有）设定下可学习的每一个分布类，是否也在 $(\varepsilon, \delta)$-差分隐私的约束下可学习？

虽然已确立纯差分隐私（$\varepsilon$-DP，其中 $\delta=0$）在可学习类与可私有学习类之间施加了严格的分离（通常由覆盖数/打包数刻画），但近似差分隐私（$(\varepsilon, \delta)$-DP）的状态仍是一个未解之谜。近期的文献提出了日益通用的私有分布学习框架，促使 Ashtiani [Ash22] 猜想上述问题的答案是肯定的：即每一个可学习的分布类都是可私有学习的。

方法论与构造
作者通过构造一个特定的分布类 $\mathcal{H}_w$ 作为反例，驳斥了这一猜想。该构造利用了一种涉及分布混合的“陷阱门”机制：

1. 类结构：类 $\mathcal{H}_{w,d}$ 由 $d+1$ 个分量的混合组成，这些分量共享一个公共参数向量 $\mathbf{p} \in [0,1]^d$。
   • “密钥”分量：一个定义在 $\{0,1\}^d$ 上的二元积分布，混合权重为 $w$。来自该分量的单个样本即可揭示关于整个参数向量 $\mathbf{p}$ 的信息。
   • “困难”分量：$d$ 个额外的分量，每个分量支撑在 $\{\pm j\}$ 上（其中 $j \in \{1, \dots, d\}$），混合权重为 $(1-w)/d$。来自其中任意一个分量的样本仅揭示关于 $\mathbf{p}$ 单个坐标的信息。
2. 陷阱门：混合权重 $w$ 被设定为 $1/(2\alpha)$（其中 $\alpha$ 是目标误差）。这确保了“困难”分量在混合中占主导地位（采样到它们的概率很高），而“密钥”分量则非常罕见。
3. 维度技巧：类 $\mathcal{H}_w$ 被定义为所有这些类在所有维度 $d \ge 2$ 上的并集。该构造确保了虽然维度 $d$ 并非先验固定，但学习的难度随 $d$ 而增加。

关键结果与证明
本文确立了类 $\mathcal{H}_w$ 在总变差（TV）距离方面，非私有可学习性与私有可学习性之间的分离：

1. 非私有可学习性（有限样本）：
   作者证明，$\mathcal{H}_w$ 可以在常数个样本（独立于 $d$）下学习，达到常数误差。

   • 机制：由于“密钥”分量以概率 $w$ 出现，非私有算法可以收集足够多的样本以观察到该密钥分量。一旦观察到，维度 $d$ 即可被识别，且参数向量 $\mathbf{p}$ 可通过二元积分布的样本均值进行估计。
   • 复杂度：样本复杂度为 $O(1/\alpha^3 \cdot \log(1/\beta))$，相对于维度 $d$ 是常数。

2. 私有不可学习性（需要无限样本）：
   作者证明，没有任何 $(\varepsilon, \delta)$-DP 机制能在有限样本下以相同的误差保证学习该类。

   • 归约：他们构造了一个从 $\mathcal{H}_{w,d}$ 上的密度估计问题到二元积分布的 $\ell_1$-参数估计问题的归约。
   • 下界：利用二元积分布私有均值估计的已知下界（具体来自 [KLSU19]），他们表明在 DP 下学习 $\mathcal{H}_{w,d}$ 的样本复杂度按 $\Omega(\sqrt{d}/(\sqrt{\alpha}\varepsilon))$ 缩放。
   • 矛盾：由于类 $\mathcal{H}_w$ 包含适用于任意 $d \ge 2$ 的分布，且所需样本量随 $\sqrt{d}$ 增长，因此没有任何有限的样本量 $n$ 足以在 DP 下学习整个类 $\mathcal{H}_w$。随着 $d \to \infty$，所需样本量趋向于无穷大。

主要贡献

• 驳斥猜想：本文提供了明确的反例，驳斥了 Ashtiani 关于在 $(\varepsilon, \delta)$-DP 下每一个可学习分布类都是可私有学习的猜想。
• 可学习性的分离：它展示了一种严格的分离，即一个类在非私有情况下仅需 $O(1)$ 个样本即可学习，但在私有情况下学习则需要无限个样本。
• 陷阱门构造：作者引入了一种特定的“陷阱门”构造，其中一个罕见分量充当高维参数的“密钥”，而该参数通常被一个占主导地位且难以学习的分量所掩盖。这种结构阻止了私有机制在不违反隐私约束或需要禁止性样本量的情况下访问该“密钥”。

意义与主张
本文声称“弱驳斥”了该猜想。作者明确指出，“强驳斥”需要证明该类在任意目标误差（而不仅仅是常数误差）下，非私有学习均可在有限样本内完成，而他们并未证明这一点。然而，他们的结果具有重要意义，因为它表明即使对于常数误差保证，私有分布学习的图景也与非私有学习有着根本的不同。

这项工作强调，私有学习的通用框架不能简单地依赖于从非私有学习器出发的黑盒归约，而无需额外的结构假设。它确立了这样一个事实：存在一种罕见但对学习至关重要的“密钥”分量，这可能会为私有算法制造无法逾越的障碍，即使非私有算法是高效的。

结论
本文得出结论：设计适用于所有可学习分布类的通用私有学习算法的议程无法完全实现。存在一些可学习类，其中隐私约束从根本上将样本复杂度从有限改变为无限，无论具体的误差容限如何（在所考虑的常数范围内）。