Better Locally Private Sparse Estimation Given Multiple Samples Per User

Understand

Previous studies yielded discouraging results for item-level locally differentially private linear regression with $s^*$-sparsity assumption, where the minimax rate for $nm$ samples is $\mathcal{O}(s^{*}d / nm\varepsilon^2)$.

• This can be challenging for high-dimensional data, where the dimension $d$ is extremely large.
• In this work, we investigate user-level locally differentially private sparse linear regression.
• We show that with $n$ users each contributing $m$ samples, the linear dependency of dimension $d$ can be eliminated, yielding an error upper bound of $\mathcal{O}(s^{*2} / nm\varepsilon^2)$.