双方是否应合并数据？隐私评估数据共享的算法与极限

论文研究两方在 ε-双方差分隐私下、不向对方泄露各自数据点的前提下，判断能否用同一分类器联合拟合双方数据。对实数域上规模为 m 的阈值，最优错误阈值 t 为 Õ(log log m/ε)，远小于隐私学习阈值所需的 Θ(log m/ε)。对 ℝ^d 中的半空间，给出 t=Õ(d³log m/ε) 的协议，并证明某些域需 t=Ω(d log(m/d)/ε)。