离散分布学习算法提出

发生了什么

据arXiv cs.LG，研究人员提出离散分布学习在个人级差分隐私下的高效最优算法，给出纯与近似差分隐私下的样本复杂度保证。在纯$(\varepsilon,0)$-DP下，算法达到$n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k/\varepsilon)$，首次匹配信息理论最优。在近似$(\varepsilon,δ)$-DP下，算法为$n = \widetilde O(k/(α^2 m)+k/(α\sqrt{m}\varepsilon)+k+\log(1/δ)/\varepsilon)$。