arXiv揭示差分隐私在线学习与预测复杂度分离

发生了什么

据arXiv论文，研究证明在Littlestone类中，差分隐私在线学习与在线预测的样本复杂度存在分离界限。论文指出，对于任意有限Littlestone维度d，两者复杂度差异随时间视界增长。具体而言，任何(ε,δ)-私有在线学习者在确定性可实现流上的错误界至少为O(d/ε log^(2/3) T)。同时，存在(ε,δ)-联合私有预测器，其期望错误数最多为2^(2^(cd^2)) ε^(-2) log^2(2/(εδ))，且独立于T。