洗牌差分隐私下稀疏线性模型的极限与近优算法
On the Limits of Sparse Linear Model with Shuffled Differential Privacy
AI 导读
论文研究稀疏线性回归在非交互与交互洗牌差分隐私（SDP）下的估计极限。非交互设定中，任意 (ε,δ)-SDP 的 ℓ2 误差下界为 Ω(√(dk)/(nε))，存在固有维度障碍；用户级交互设定下提出两轮算法，误差不含维度 d 的多项式依赖。论文还将 score attack 扩展至用户级数据证明新下界，显示该算法在 log(d/k) 因子内近优。