Limits and near-optimal algorithms for sparse linear models under shuffled differential privacy
On the Limits of Sparse Linear Model with Shuffled Differential Privacy
AI summary
The paper studies the estimation limits of sparse linear regression under non-interactive and interactive shuffled differential privacy (SDP). In the non-interactive setting, the ℓ2 error lower bound for any (ε,δ)-SDP is Ω(√(dk)/(nε)), and an inherent dimensionality barrier exists; in the user-level interactive setting, a two-round algorithm is proposed whose error contains no polynomial dependence on the dimension d. The paper also extends the score attack to user-level data to prove a new lower bound, showing that the algorithm is near-optimal within a log(d/k) factor.