个人级隐私下离散分布的高效最优学习

arXiv:2610.31612v1 公告类型：新论文 摘要：我们研究批量场景下满足个人级差分隐私的离散分布学习问题。给定 $n$ 个用户，每个用户提供从 $[k]$ 上的未知分布 $\mu$ 中独立同分布抽取的 $m$ 个样本，我们希望得到 $\mu$ 的估计，使其总变差误差为 $\alpha$。我们分别给出满足纯差分隐私和近似差分隐私的多项式时间算法。在纯 $(\varepsilon,0)$-DP 下，我们达到 $n = \widetilde O(k/(\alpha^2 m)+k/(\alpha\sqrt{m}\varepsilon)+k/\varepsilon)$，这是首个在相差对数因子的意义下达到信息论最优界的多项式时间纯差分隐私保证。在近似 $(\varepsilon,\delta)$-DP 下，我们达到 $n = \widetilde O(k/(\alpha^2 m)+k/(\alpha\sqrt{m}\varepsilon)+k+\log(1/\delta)/\varepsilon)$。当 $\delta=2^{-\Theta(k)}$ 时，对于固定的 $\alpha,\varepsilon,m$ 和失败概率，该界为 $\widetilde O(k)$。我们的算法使用一种新的六次平方和估计器，从不可信批次中进行学习。其关键组成部分是一个迹有界的对角上界矩阵，用于控制修复后的批次均值的经验协方差与由其均值预测的多项分布协方差之差。我们通过半正定规划对偶性，以及对 Friedland 和 Lim 提出的更强对称形式的 Grothendieck 不等式的新应用，证明干净数据具有这一证书。该证书保留了多项分布批次均值中依赖于均值的方差，从而得到近乎最优的鲁棒误差率 $O(\eta\sqrt{\log(1/\eta)/m})$，并提供隐私归约所需的评分。我们还证明了一个统计查询下界，排除了在固定的多项式 SQ 资源约束下实现一致更低误差阶的可能性。