人物级差分隐私下离散分布学习的高效最优算法

论文给出人物级差分隐私（person-level DP）下批量设定离散分布学习的多项式时间算法，纯 (ε,0)-DP 下达到 n = Ō(k/(α²m)+k/(α√m·ε)+k/ε)，首次在对数因子内匹配信息论最优。近似 (ε,δ)-DP 下当 δ=2^{-Θ(k)} 时样本复杂度为 Ō(k)。算法采用 6 阶 sum-of-squares 估计器，并证明多项式 SQ 资源下更小误差阶的下界。