  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)$. We propose a
framework that first selects candidate variables and then conducts estimation
in the narrowed low-dimensional space, which is extendable to general sparse
estimation problems with tight error bounds. Experiments on both synthetic and
real datasets demonstrate the superiority of the proposed methods. Both the
theoretical and empirical results suggest that, with the same number of
samples, locally private sparse estimation is better conducted when multiple
samples per user are available.
