arXiv· Yan Zhang·· 7 天前推荐指数30
Shuffled Differential Privacy 下稀疏线性回归的误差下界与两轮交互算法
On the Limits of Sparse Linear Model with Shuffled Differential Privacy
AI 导读
论文证明任何非交互式 (ε,δ)-SDP 协议在稀疏线性回归上都存在 Ω(√(dk)/(nε)) 的 ℓ₂ 估计误差下界，揭示固有的维度障碍。为此提出两轮交互式用户级算法，先用 heavy hitter 步骤恢复支撑集再估计参数，误差为 Õ(√(k/(nm)) + k/(n√m·ε))，对维度 d 无多项式依赖。
来源：arXiv · arxiv.org